Merging Overlapping Intervals

Merging Overlapping Intervals

Imagine you have a list of time slots. Maybe one meeting runs from 1 PM to 4 PM, another from 2 PM to 3 PM, and so on. Some of these slots overlap — they share part of the same time. The goal of this problem is to combine all the overlapping slots into clean, separate blocks that have no overlap at all.

What is an interval?

An interval is just a pair of numbers that marks a start and an end. We write it like [s, e], where s is the start and e is the end.

For example, [1, 4] means "begins at 1, ends at 4". Think of it as a line segment stretching from point 1 to point 4 on a ruler.

You are given a whole array of these intervals:

intervals[i] = [si, ei]

Your task is to merge every group of overlapping intervals and return a new list where none of the intervals overlap anymore — but together they still cover everything the original list covered.

When do two intervals overlap?

This is the key rule of the whole problem. Two intervals [s1, e1] and [s2, e2] overlap when:

e1 >= s2

In plain words: if the end of the first interval reaches (or goes past) the start of the second interval, they touch or cross, so they overlap. When they overlap, you can squash them together into one bigger interval that runs from the smallest start to the largest end.

Walking through Example 1

Input:

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

Let's see why they all collapse into one:

• [2, 3] sits completely inside [1, 4] (it starts after 1 and ends before 4), so it adds nothing new. Merge it away.
• [3, 4] also lies inside [1, 4] for the same reason. Merge it away.
• Now look at [1, 4] and [4, 6]. The end of the first is 4, and the start of the second is 4. Since 4 >= 4, they touch — so they overlap. Joining them gives [1, 6].

After all the merging, everything from 1 to 6 is covered by a single block:

Output: [[1, 6]]

You may return the answer in any order — the order of intervals in your output list does not matter.

The function you must write

The starter code gives you a C++ class:

using namespace std;
class Solution {
public:
    vector<vector<int>> overlapReduction(vect ) {
    }
};

You take in the list of intervals and return a vector<vector<int>> — a list of [start, end] pairs with no overlaps left.

A simple way to think about solving it

A common, beginner-friendly plan:

1. Sort the intervals by their start value. This lines them up left to right, so overlaps always appear next to each other.
2. Keep the last interval you have finished so far.
3. For each new interval, check the overlap rule. If its start is <= the current end, stretch the current end to the larger of the two ends. If not, the current block is done — save it and start a fresh block.

Sorting first is what makes this easy: once everything is in order, you only ever need to compare each interval with the one right before it.