💬 Discord
Sign In
NeetCode #834LC-435MediumIntervalsBlind 75NC 150NC 250
← Back to All Problems

#834 · #435 · Non-overlapping Intervals(无重叠区间)

📌 Problem Statement & Constraints

You are given an array of intervals intervals. Return the minimum number of intervals you must remove to make the rest non-overlapping. Intervals that merely touch (one ends where the next begins) do not overlap. Constraints: 1 <= intervals.length <= 10^5, -5 * 10^4 <= intervals[i][0] < intervals[i][1] <= 5 * 10^4.

💡 Core Algorithmic Approaches

  1. This is the classic interval-scheduling problem: maximise the number of kept intervals, then subtract from n.
  2. Sort by end time, since finishing early leaves the most room for later intervals.
  3. Greedily keep an interval whenever its start is at least the last kept end, and update the running end.
  4. The exchange argument: replacing any kept interval with the earliest-ending compatible one never reduces the number of future choices, so the greedy is optimal.

💻 Benchmark Python3 Implementation

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])      # earliest finishing first
        removed = 0
        prev_end = float("-inf")
        for s, e in intervals:
            if s >= prev_end:                   # compatible -> keep it
                prev_end = e
            else:
                removed += 1                    # overlaps the last kept one
        return removed

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort by end dominates.
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting by start: the optimal greedy requires the earliest finishing interval, so the sort key must be the end.
  • Using s > prev_end: touching intervals are allowed, so the test is s >= prev_end.
  • Returning the number kept: the question asks how many to remove, which is n - kept.
  • Initialising prev_end to 0: intervals can be negative, so a sentinel like -inf is required.