Merge Intervals

Leave a comment

December 18, 2016 by oneOokay

Given a collection of intervals, merge all overlapping intervals.

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


这个跟会议室II那个很像,但是也有不同。

我自己写了个比较复杂的版本pass了:

  1. 一个priority queue来对list进行排序(其实可以用Collections.sort)
  2. 一个priority queue来存结果的interval
  3. 再把最后priority queue里面的intervals倒到list里面返回。

最佳版本呢:(除了也有一个目前理解无能的super easy 的解法以外)

  1. 用Collections.sort
  2. 直接for-loop循环加到ans里
  3. 同时track overlapping的start和end
public List merge(List intervals) {
        List ans = new ArrayList();
        if (intervals == null || intervals.size() == 0){
            return ans;
        }
        
        Collections.sort(intervals, new Comparator(){
           public int compare(Interval i1, Interval i2){
               if (i1.start != i2.start){
                   return i1.start - i2.start;
               }
               if (i1.start == i2.start && i1.end != i2.end){
                   return i1.end - i2.end;
               }
               return 0;
           } 
        });
        
        int start = intervals.get(0).start; 
        int end = intervals.get(0).end;
        for (Interval i : intervals){
            if (i.start <= end){
                end = Math.max(i.end, end);
            }else {
                ans.add(new Interval(start, end)); //加入前一个的start和end
                start = i.start;//重设start和end为下一个做准备
                end = i.end;
            }
        }
        ans.add(new Interval(start, end));//加入最后一个interval
        return ans;
    }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: