题解 | #合并区间#
合并区间
http://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a
思路:先按区间左边界按升序排序,用Collections.sort();
1.设置双指针,一个指向当前已合并过的末尾的区间p,一个指向还未合并过的第一个区间q。
2.比较q的start值与p的end值的大小
1)若q.start<=p.end,取p.end与q.end的最大值赋给p.end,并删除q。删除后就相当于进行了q++,因此不需要额外的q++了。
2)若q.start>p.end,说明不重合。p++,q++。
public ArrayList<Interval> merge(ArrayList<Interval> intervals) { Collections.sort(intervals,new Comparator<Interval>(){ @Override public int compare(Interval o1,Interval o2){ return o1.start-o2.start; } }); int p=0; int q=1; while(q<intervals.size()){ Interval ip=intervals.get(p); Interval iq=intervals.get(q); if(iq.start<=ip.end){ ip.end=Math.max(iq.end,ip.end); intervals.remove(q); }else{ p++; q++; } } return intervals; }