import java.util.*; /* * public class Interval { * int start; * int end; * public Interval(int start, int end) { * this.start = start; * this.end = end; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param intervals Interval类ArrayList * @return Interval类ArrayList */ public ArrayList<Interval> merge (ArrayList<Interval> intervals) { // write code here //res用来保存最终需要返回的结果 ArrayList<Interval> res = new ArrayList<>(); if(intervals.size()==0) return res;//排除特殊情况 //对intervals中的区间进行升序排序,start相同的按end排 Collections.sort(intervals,new Comparator<Interval>() { public int compare(Interval n1,Interval n2) { if(n1.start!=n2.start) return n1.start-n2.start; else return n1.end-n2.end; } }); res.add(intervals.get(0));//先加入第一个区间 int count=0;//永远指向res中最后一个元素 for(int i=1;i<intervals.size();i++) { Interval cur = intervals.get(i); Interval pre = res.get(count); if(cur.start>pre.end)//无需合并,将cur加入res { res.add(cur); count++; } else//需要合并 { res.remove(count);//先从res中移除最后一个区间 Interval tmp =new Interval(pre.start,Math.max(cur.end,pre.end));//合并得到的新区间 res.add(tmp); //注意这里删一加一,count不需要++ } } return res; } }