Neetcode 150 - Non-overlapping Intervals

1. Input, Output, Contraints

  1. Input:
Input: intervals = [[1,2],[2,4],[1,4]]
  1. Output:
Output: 1
  • After [1,4] is removed, the rest of the intervals are non-overlapping.
  1. Contraints:
  • 1 <= intervals.length <= 1000
  • intervals[i].length == 2
  • 50000 <= starti < endi <= 50000

2. Intuition

2.1. Why do not sort by start_time but sort by end_time ?

Sort Order	Intuition	Result
By start time	process intervals from earliest start	❌ can lead to suboptimal choices
By end time	process intervals that finish earliest	✅ guaranteed optimal (greedy)
  • For example, [1,2] and [1,5] is overlapped suboptimal choices

=> We greedy by end time.

Now, greedy rule:

  • Always pick the interval that ends earliest, skip any that overlap with it.
Step	Interval	prev_end	Overlap?	Kept
1	[2,3]	—	—	✅
2	[3,4]	3	no	✅
3	[4,5]	4	no	✅
4	[1,10]	5	yes	❌

3. Implement O(NlogN), sort by end_time

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        # Step 1: Sort by end time
        intervals.sort(key=lambda x: x[1])

        prev_end = intervals[0][1]
        count = 0  # removals

        # Step 2: Greedy selection
        for i in range(1, len(intervals)):
            start, end = intervals[i]
            if start < prev_end:  # Overlap → remove this interval
                count += 1
            else:                 # No overlap → keep it
                prev_end = end

        return count
Last Updated On October 17, 2025