[LC 435]. Non-overlapping Intervals

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

两点:
1.sort intervals by their ends. Why not starts? Draw a picture with some overlapping intervals and see.

a |________|
b |_________|
c |_________|
If interval a overlap with b, dump b, and check a and c. Because if c overlap with a, it will overlap with b for sure (if c.start < a.end, then c.start a.end). However if sort by start, when a and b overlap, need to check both pair (a, c) and (b, c), since the following case is possible:
a |___________|
b |__|
c |______|

2.finding minimum number of intervals to be removed, equals to finding max number of non-overlapping intervals

    public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals == null || intervals.length < 2) return 0;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2) {
                return i1.end - i2.end;
            }
        });
        
        int count = 1; // max number of non-overlapping intervals
        int end = intervals[0].end;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start >= end) {
                end = intervals[i].end;
                count++;
            }
        }
        
        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