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那个很像,但是也有不同。

  • 用Collections.sort对intervals进行排序.
  • 直接for-loop循环加到ans里,把当前的interval和前一个interval进行比较.
  • 同时track overlapping的start和end

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

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

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

public List merge(List intervals) {
        List ans = new ArrayList();
        if (intervals == null || intervals.size() == 0){
            return ans;
        }
        //排序:comparator的简单的写法.
        Collections.sort(intervals, (a,b)->a.start == b.start ?
a.end - b.end : a.start - b.start);        
        Interval pre = intervals.get(0);
 for (int i = 1; i< intervals.size(); i ++){
 if (intervals.get(i).start <= pre.end){
 pre.end = Math.max(intervals.get(i).end, pre.end);
 }else{
 res.add(pre);
 pre = intervals.get(i);
 }
 }
//注意最后不要忘了加入pre.
 res.add(pre);
 return res;
    }

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: