题解 | #合并区间#
合并区间
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;
}
投递三维家等公司10个岗位