首页 > 代码库 > leetcode 57 Insert Interval ----- java

leetcode 57 Insert Interval ----- java

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

这道题和上面的一道题是类似题,就是给定数个排序好的数组和一个单独的数组,将单独的数组插入那个数组集合中,并且合并相关的集合。

第一次写的就是找到开始插入的地方begin和插入结束的地方last,然后删除并且合并,但是结果并不是很理想。

/** * Definition for an interval. * public class Interval { *     int start; *     int end; *     Interval() { start = 0; end = 0; } *     Interval(int s, int e) { start = s; end = e; } * } */public class Solution {                public List<Interval> insert(List<Interval> intervals, Interval newInterval) {                int start = newInterval.start,end = newInterval.end,len = intervals.size();        int begin = 0, last = len-1;        if( len == 0){            intervals.add(newInterval);            return intervals;        }        while( begin<len && intervals.get(begin).end < start )            begin++;        if( begin == len){            intervals.add(newInterval);            return intervals;        }        while( last>=0 && intervals.get(last).start > end )            last--;        //from begin to last        if( begin > last){            intervals.add(begin, newInterval);            return intervals;        }       Interval ans = new Interval();        ans.start = intervals.get(begin).start>newInterval.start?newInterval.start:intervals.get(begin).start;        ans.end = intervals.get(last).end>newInterval.end?intervals.get(last).end:newInterval.end;        intervals.set(begin, ans);        for( int i = begin+1;i<=last;i++){            intervals.remove(begin+1);            }                        return intervals;    }    }

然后做了一点改变,就是last不从最后开始算起,而是从begin开始的地方算起,结果速度更慢了= =。。。。。

/** * Definition for an interval. * public class Interval { *     int start; *     int end; *     Interval() { start = 0; end = 0; } *     Interval(int s, int e) { start = s; end = e; } * } */public class Solution {            public List<Interval> insert(List<Interval> intervals, Interval newInterval) {        int start = newInterval.start, end = newInterval.end, len = intervals.size();        int begin = 0, last = 0 ;        if (len == 0) {            intervals.add(newInterval);            return intervals;        }        if ( end < intervals.get(0).start ){            intervals.add(0, newInterval);            return intervals;        }        if ( start > intervals.get(len-1).end){            intervals.add(newInterval);            return intervals;        }        while ( start > intervals.get(begin).end)            begin++;        last = begin;        while ( last < len && end >= intervals.get(last).start )            last++;        if( begin == last ){            intervals.add(begin,newInterval);            return intervals;        }        start = intervals.get(begin).start>start?start:intervals.get(begin).start;        end = intervals.get(last-1).end>end?intervals.get(last-1).end:end;        for ( int i = 1;i<last-begin;i++)            intervals.remove(begin);        intervals.get(begin).start = start;        intervals.get(begin).end = end;        return intervals;                            }}

估计效率如此低的缘故,应该是remove操作造成的,因为每一次remove操作是将该元素删除之后,再将之后的所有元素向前移动一次,所以效率很低。

所以改变直接remove的方式,改为先将后面的集合移动过来,然后再从后向前删除集合。这样效率就很高了。

/** * Definition for an interval. * public class Interval { *     int start; *     int end; *     Interval() { start = 0; end = 0; } *     Interval(int s, int e) { start = s; end = e; } * } */public class Solution {            public List<Interval> insert(List<Interval> intervals, Interval newInterval) {        int start = newInterval.start, end = newInterval.end, len = intervals.size();        int begin = 0, last = 0 ;        if (len == 0) {            intervals.add(newInterval);            return intervals;        }        if ( end < intervals.get(0).start ){            intervals.add(0, newInterval);            return intervals;        }        if ( start > intervals.get(len-1).end){            intervals.add(newInterval);            return intervals;        }        while ( start > intervals.get(begin).end)            begin++;        last = begin;        while ( last < len && end >= intervals.get(last).start )            last++;        if( begin == last ){            intervals.add(begin,newInterval);            return intervals;        }        intervals.get(begin).start = intervals.get(begin).start>start?start:intervals.get(begin).start;        intervals.get(begin).end = intervals.get(last-1).end>end?intervals.get(last-1).end:end;        for( int i = 0;i<len-last;i++)            intervals.set(begin+1+i,intervals.get(last+i));        for ( int i = 1;i<last-begin;i++)            intervals.remove(len-i);        return intervals;                            }}

 

leetcode 57 Insert Interval ----- java