Problem statement

https://binarysearch.com/problems/Remove-Interval-Overlaps/

Solution

Equal to Leetcode 0435. Non-overlapping Intervals.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(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