Skip to main content

26. Non-overlapping Intervals

mediumAsked at Unity

Find the minimum number of intervals to remove so the rest don't overlap — the same greedy scheduling pass Unity's physics scheduler uses to drop the fewest collision-event callbacks so the fixed-update budget is never exceeded.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest non-overlapping.

Constraints

  • 1 <= intervals.length <= 10^5
  • -5 * 10^4 <= start_i < end_i <= 5 * 10^4

Examples

Example 1

Input
intervals = [[1,2],[2,3],[3,4],[1,3]]
Output
1

Explanation: Remove [1,3] to leave three non-overlapping intervals.

Example 2

Input
intervals = [[1,2],[1,2],[1,2]]
Output
2

Approaches

1. Greedy by earliest end time

Sort by end time. Greedily keep every interval whose start >= last kept end. Count removals as total - kept.

Time
O(n log n)
Space
O(1)
function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let kept = 0;
  let lastEnd = -Infinity;
  for (const [s, e] of intervals) {
    if (s >= lastEnd) {
      kept++;
      lastEnd = e;
    }
  }
  return intervals.length - kept;
}

Tradeoff:

Unity-specific tips

Unity looks for the greedy insight that sorting by end time (not start) maximises compatible intervals kept — phrase it as preferring the callback that 'finishes earliest' so you have the most room for the next one, exactly how a fixed-update scheduler prioritises short-running physics events.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Non-overlapping Intervals and other Unity interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →