DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Non-overlapping Intervals - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        res = 0
        prev_end = intervals[0][1]
        for start, end in intervals[1:]:
            if start < prev_end:
                res += 1
                prev_end = min(end, prev_end)
            else:
                prev_end = end
        return res

Complexity Analysis

Here, n represents the number of intervals in the input array.

  • Time Complexity: O(n log n), dominated by the sorting step.
  • Space Complexity: O(1) or O(n) depending on whether sorting is done in place or not.