[leetcode] Merge Intervals | 带overlap的interval数组，把overlap那些都merge了。

Posted by: lexigrey on: August 1, 2013

• In: leetcode
• Leave a Comment

今天又被assign了不归我的活，怒了。干脆上班不工作了，直接刷题。

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [2,6],[1,3],[8,10],[15,18],
return [1,6],[8,10],[15,18].

思路：先sort by start，然后不断判断当前的interval能不能吞噬下一个(curr.end >= next.start，说明这两个能连起来）。做的过程中发现几个问题：

1. 本来是想直接循环list，然后不断吞噬，删掉被吞噬的。但是这样就一边iterate一边modify array了，会挂。所以还得用另一个list，然后决定是不断删list2里的东西，还是不断往list2里加东西。这个要拿例子试试哪种好使。
2. 一开始写的是if (curr.end >= next.start) then curr.end = next.end。然后挂了几个test case，才注意到忘记了curr本身包括了next的情况。应该是curr.next = Math.max(curr.end, next.end)
3. 第一次写java inline的comparator!

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
  Collections.sort(intervals, new Comparator<Interval>() {
    public int compare(Interval a, Interval b) {
      return a.start - b.start;
    }
  });
  ArrayList<Interval> result = new ArrayList<Interval>();
  for (int i = 0; i < intervals.size(); i++) {
    Interval curr = intervals.get(i);
    while (i < intervals.size() - 1 && curr.end >= intervals.get(i + 1).start) {
      curr.end = Math.max(curr.end, intervals.get(i + 1).end);
      i++;
    }//while出来说明curr已经吃饱了，可以加入result了。
    result.add(curr);
  }
  return result;
}

Tags: array, easy, math