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].
因为这道题目和56题大部分相同，就放在这一块写了。57题相较于56只是多了一个在list中插入Interval的操作。
主要还是用到了merge函数的部分。主要的思路是先通过将list进行一次排序，然后再通过start和end的位置，来进行合并。这道题主要学习了comparator接口的使用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
|
public class { public List<Interval> insert(List<Interval> intervals, Interval newInterval) { List<Interval> res=new ArrayList<>(); if(intervals.size()==0){ res.add(newInterval); return res; } intervals.add(newInterval); res=merge(intervals); return res; } public List<Interval> merge(List<Interval> intervals) { if(intervals==null||intervals.size()<=1){ return intervals; } Collections.sort(intervals,new IntervalComparator()); List<Interval> res=new ArrayList<Interval>(); Interval last=intervals.get(0); for(int i=1;i<intervals.size();i++){ Interval curr=intervals.get(i); if(curr.start<=last.end){ last.end=Math.max(last.end,curr.end); }else { res.add(last); last=curr; } } res.add(last); return res; } public class IntervalComparator implements Comparator<Interval>{ public int compare(Interval a,Interval b){ return a.start-b.start; } } }
|
近期评论