435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

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

Note: The idea is simple but not obvious to prove.

Sort by end points and pick one by one without overlap.

      This means, the longer end points are getting discarded.

def eraseOverlapIntervals(self, intervals: List[List[int]]):

       

    if not intervals:

        return 0;

   

    intervals = sorted(intervals, key=lambda x: x[1])

           

    end = intervals[0][1]

    take = 1 <----------------------------------Note

   

    for interval in intervals[1:]:

        if interval[0] >= end:

            end = interval[1]

            take += 1

           

    return len(intervals) - take