Skip to main content

25. Non-overlapping Intervals

mediumAsked at Expedia

Find the minimum number of intervals to remove so none overlap — Expedia uses this greedy pruning to eliminate conflicting layover windows when building the tightest valid itinerary.

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

Problem

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals 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 make the rest non-overlapping.

Example 2

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

Approaches

1. Brute force (try all subsets)

Check every subset for the non-overlapping property; track the minimum removals. Exponential — useful only to establish correctness.

Time
O(2^n)
Space
O(n)
function eraseOverlapIntervals(intervals) {
  const n = intervals.length;
  let minRemove = n;

  function isNonOverlapping(subset) {
    for (let i = 1; i < subset.length; i++) {
      if (subset[i][0] < subset[i - 1][1]) return false;
    }
    return true;
  }

  for (let mask = 0; mask < (1 << n); mask++) {
    const kept = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) kept.push(intervals[i]);
    }
    kept.sort((a, b) => a[0] - b[0]);
    if (isNonOverlapping(kept)) {
      minRemove = Math.min(minRemove, n - kept.length);
    }
  }
  return minRemove;
}

Tradeoff:

2. Greedy — sort by end time

Sort by end time; greedily keep intervals with the earliest end that do not overlap the previous kept interval. Count what's removed.

Time
O(n log n)
Space
O(1)
function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);

  let removed = 0;
  let lastEnd = -Infinity;

  for (const [start, end] of intervals) {
    if (start >= lastEnd) {
      lastEnd = end;
    } else {
      removed++;
    }
  }

  return removed;
}

Tradeoff:

Expedia-specific tips

Expedia's itinerary-optimization team expects the greedy insight immediately: always keep the interval that ends earliest, because it leaves the most room for future intervals. Sorting by end time (not start) is the subtle key — interviewers will probe that choice. Map it to layover scheduling: keep the layover that finishes first to maximize downstream flight options.

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 Expedia interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →