Remove Intervals: Making Intervals Non-Overlapping

Remove Intervals: Making Intervals Non-Overlapping

Imagine you are booking meeting rooms. Each meeting has a start time and an end time. If two meetings happen at the same time, they clash — you cannot keep both in one room. To fix the clashes, you have to cancel some meetings. This problem asks: what is the smallest number of meetings you must cancel so that none of the remaining ones clash?

What is an interval?

An interval is just a small range with a start and an end. We write it as a pair of numbers, like [1, 2]. Here 1 is the start and 2 is the end.

In this problem you are given a list of intervals:

intervals[i] = [si, ei]

This simply means: the interval at position i starts at si and ends at ei.

The goal

Your job is to find and return the minimum number of intervals you need to remove so that the rest of the intervals do not overlap. "Non-overlapping" means no two leftover intervals share any time.

When do two intervals overlap?

This is the most important rule, and it has a small twist:

> Two intervals [s1, e1] and [s2, e2] are considered overlapping if e1 > s2.

> If e1 == s2, they are not overlapping.

Let's read that slowly. Suppose the first interval ends at time e1 and the second one starts at time s2.

• If the first one is still going when the second one starts (e1 > s2), they clash — overlap.
• If the first one ends exactly when the second one starts (e1 == s2), they just touch at a single point. The rule says this is fine — not an overlap.

Think of it like back-to-back meetings: one ends at 3:00 and the next starts at 3:00. They don't really collide, so we allow it.

Example 1

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

Let's see why the answer is 1. Look at the four intervals:

• [1, 2] then [2, 3]: the first ends at 2 and the next starts at 2. They only touch — no overlap.
• [2, 3] then [3, 4]: again they only touch at 3 — no overlap.
• [1, 3]: this one stretches from 1 to 3. It sits on top of [1, 2] and [2, 3], so it clashes with them.

If we simply remove [1, 3], the three remaining intervals [1, 2], [2, 3], [3, 4] line up neatly without clashing. We only had to remove one interval, so the answer is 1.

How to think about solving it

A common, simple idea is:

1. Sort the intervals by their end value, so the ones that finish earliest come first.
2. Keep track of the end of the last interval you decided to keep.
3. Go through the intervals one by one. If the current interval starts at or after that last end (no clash), keep it and update the last end. If it starts too early (it clashes), remove it and add one to your counter.

The number you counted is the minimum number of removals. The starting code you are given is a C++ function:

class Solution {
public:
    int removeIntervals(vector<vector<int>> &
};

The function takes the list of intervals and should return that single number — the fewest intervals to delete so the rest no longer overlap.