Non-overlapping Intervals

Leave a comment

December 18, 2016 by oneOokay

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

  1. You may assume the interval’s end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

这题乍看上去跟之前的intervals和overlapping的都差不多,但是其实不太一样。

这题求最少需要移除的interval数目,其实就是等同于求集合中存在最多的non-overlapping interval的数目。

其实也就是求我们有这么些个任务,可能存在overlapping,求最多能够完成多少个任务这样类似的题目。

这个是一个Classic Greedy problem,如果像之前的题目一样把intervals按照start time排列,并不能达到目的。因为如果最早开始的task恰好持续的时间最长,那么并不能得到最优解。所以应该按照task的结束顺序进行排列。

public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals == null || intervals.length <= 1){
            return 0;
        }
        Arrays.sort(intervals, new Comparator<Interval>(){
           public int compare(Interval i1, Interval i2){
                   return i1.end - i2.end;
           }
        });
        
        int end = intervals[0].end;
        int count = 1; //注意初始的count=1,因为至少为1
        for(int i = 1; i < intervals.length; i++){
             Interval cur = intervals[i];
             if (cur.start >= end){
                count ++;
                end = cur.end;
            }
        }
        return intervals.length - count;
    }
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: