Non Overlapping Intervals

The problem

intervals is a list of intervals, each written [start, end] with start less than end. Two intervals overlap when each of them starts before the other ends. So [1, 3] and [2, 4] overlap, and so do two copies of the same interval, but [1, 2] and [2, 3], which only touch at 2, do not. Return the smallest number of intervals you must remove so that no two of the remaining ones overlap. The list may be empty, which gives 0, and numbers may be negative.

What to write

function solve(intervals: number[][]): number

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

Output
1

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

Output
2

Constraints

0–1,000 intervals with start < end; touching endpoints are allowed.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Removing as few intervals as possible is the same as keeping as many as possible. Intervals that only touch do not overlap, so [1, 2] and [2, 3] can both stay. Trying every subset is out: 1,000 intervals have 2 to the power 1,000 subsets.

2. Hint 2: Ask a smaller question

   Take [1, 10], [2, 3] and [3, 4]. Two of them can stay. Which one has to go, and what is it about that interval that makes it the worst one to keep?

3. Hint 3: Name the pattern

   You want to keep as many intervals as possible, and one rule is always safe: of the intervals you could keep next, take the one that ends first, because it leaves the most room. Deciding on the spot by one rule and never taking the decision back is a greedy choice. So visit the intervals in order of end. Read the lesson on greedy choice.

4. Hint 4: State the invariant

   The kept intervals never overlap. And after each interval, no other choice from the intervals visited so far keeps more of them, or keeps as many and ends earlier. That is why one number, the end of the last kept interval, is all you carry.

5. Hint 5: Sketch the pseudocode

   Sort the intervals by end. kept end = minus infinity, which is below every start, and removed = 0. For each interval [s, e] in that order: if s is less than kept end, add 1 to removed. Otherwise set kept end = e. Return removed.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Sort by finishing time and keep the earliest-finishing compatible interval. Count intervals whose starts fall before the end already kept.

The slow way

Try every subset of the intervals, check that no two intervals in it overlap, and remember the largest such subset. The answer is the number of intervals left out of it. That is correct, but n intervals have 2 to the power n subsets, which is out of reach long before n is 1,000.

The insight

Among all the intervals, look at the one that ends first, and call it E. Take any set of intervals with no overlaps, and swap E in for the set's own interval that ends first. Nothing new overlaps, because E ends no later. So keeping E is never a mistake, and the same reasoning applies again to the intervals that start at or after E's end.

Step by step

1. Start with no interval kept and none removed. The end of the last kept interval starts at minus infinity, a value below every number, so the first interval can never seem to overlap. The count of removed intervals starts at zero.
2. Visit the intervals from the earliest end to the latest. Of the intervals you could still keep, the one that ends first leaves the most room for the rest. In order of end, that is the first one you meet that overlaps nothing kept. The sort works on a copy.
3. It starts before the last kept interval ends: remove it. The two overlap, so one of them must go. The kept one ends no later than this one, so it blocks nothing that this one would leave free. Removing this one is never the worse choice.
4. Otherwise keep it and remember where it ends. It starts at or after the kept end, so it overlaps nothing that was kept. Touching is allowed. Its end is the latest among the kept intervals, so later intervals are compared with it.
5. Return how many intervals were removed. Every interval was either kept or counted. The kept ones do not overlap and no choice keeps more, so the count is the smallest number of removals.

The same numbered steps are the comments in each solution.

function solve(intervals) {
  // 1. Start with no interval kept and none removed
  let end = -Infinity,
    removed = 0;
  // 2. Visit the intervals from the earliest end to the latest
  for (const [a, b] of [...intervals].sort((x, y) => x[1] - y[1])) {
    // 3. It starts before the last kept interval ends: remove it
    if (a < end) {
      removed++;
    } else {
      // 4. Otherwise keep it and remember where it ends
      end = b;
    }
  }
  // 5. Return how many intervals were removed
  return removed;
}

function solve(intervals: number[][]): number {
  // 1. Start with no interval kept and none removed
  let end = -Infinity,
    removed = 0;
  // 2. Visit the intervals from the earliest end to the latest
  for (const [a, b] of [...intervals].sort((x, y) => x[1] - y[1])) {
    // 3. It starts before the last kept interval ends: remove it
    if (a < end) {
      removed++;
    } else {
      // 4. Otherwise keep it and remember where it ends
      end = b;
    }
  }
  // 5. Return how many intervals were removed
  return removed;
}

def solve(intervals):
    # 1. Start with no interval kept and none removed
    last_end = float("-inf")
    removed = 0
    # 2. Visit the intervals from the earliest end to the latest
    for start, end in sorted(intervals, key=lambda interval: interval[1]):
        # 3. It starts before the last kept interval ends: remove it
        if start < last_end:
            removed += 1
        else:
            # 4. Otherwise keep it and remember where it ends
            last_end = end
    # 5. Return how many intervals were removed
    return removed

Example 1, traced

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

Output
1

Why it works

Line up any other set of intervals with no overlaps against the kept set, each in order of end. Place by place, each kept interval ends no later than the other set's, because the pass always keeps the earliest end still allowed. So wherever the other set fits one more interval, the pass does too: it keeps the most and removes the fewest.

Time and space

Time O(n log n), extra space O(n) copied input. Sorting n intervals takes about n log n steps, and the pass after it looks at each interval once, so the time is O(n log n). The sorted copy holds all n intervals, which is the O(n) space. The pass itself stores two numbers.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Sort by end, not by start. Sorted by start, [1, 10], [2, 3], [3, 4] keeps [1, 10] first, then removes both short intervals and returns 2. The right answer is 1: remove [1, 10].
• Move the kept end only when you keep an interval. If a removed interval moves it too, [1, 3], [2, 4], [3, 5] removes [3, 5] because of [2, 4], which is already gone, and returns 2 instead of 1.
• Start the kept end below every possible start, not at 0. Starts can be negative here, and with 0 the single interval [-3, -1] is counted as removed: the answer is 1 instead of 0.

Pattern

Greedy choice. Builds on Jump Game and Merge Intervals.

Keep going