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.

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.

The Idea: This is uni-weight interval scheduling problem. Sort by finish, then increment every-time it overlaps with the previous valid interval.

Complexity: O(nlogn +n) time, O(1) space

def eraseOverlapIntervals(self, intervals):
    """
    :type intervals: List[Interval]
    :rtype: int
    """
    if len(intervals) == 0:
        return 0

    intervals.sort(key=lambda interval: interval.end)
    removal_count = 0
    prev_start = intervals[0].end
    for i in range(1, len(intervals)):
        if intervals[i].start < prev_start:
            removal_count += 1
        else:
            prev_start = intervals[i].end

    return removal_count