https://leetcode.com/problems/non-overlapping-intervals

How you can handle this problem if you see it first time? If number of segments is small, we can try to check all possible options. However in this problem number of segments can be quite big and it is not going to work. Next options are dp or greedy approaches, that we need to check, and let us try to use greedy approach. Let us try to build the longest set of non-overlapping intevals. There are different options how we can try to choose greedy strategy:

  1. The first one strategy, which is not going to work is to sort segments by its starts, but we have counterexample here: [1,100], [2,3], [3,4]: we will choose only first segment, however we can choose two of them.
  2. Another strategy is to sort segments by its ends? Why it is going to work? Let us prove it by mathematical induction: we have segments s_1, ... , s_n with sorted ends and we can choose k out of these n segments, such that they not overlap. We add s_{n+1} segment, such that its end is greater or equal than the end of s_n. How many segments we can choose out of our new n+1 segments? It can not be more that k+1, because we can choose at most k out of first n. Also, we can choose k+1 only in the case, when we take the last segment. When we can take the last segment? Only if it is not intersecting with segment number n! Because if it is intersection with some previous segment, it must intersect with segment number n: intersection of s_{n+1} with s_i means that start of s_{n+1} is more that end of s_i. and the bigger i, the bigger the end of s_i. So we always can use greedy strategy.

Complexity: time complexity is O(n log n), for sort all segments and space complexity is O(n) if we count that we use space for sorted intervals.

class Solution:
    def eraseOverlapIntervals(self, intervals):
        intervals.sort(key = lambda x: x[1])
        n, count = len(intervals), 1
        if n == 0: return 0
        curr = intervals[0]
        
        for i in range(n):
            if curr[1] <= intervals[i][0]:
                count += 1
                curr = intervals[i]
                
        return n - count

If you like the solution, you can upvote it on leetcode discussion section: Problem 0435