Merging Overlapping Intervals with the Line Sweep Technique

What "merging intervals" means

An interval is just a small range that has a start and an end. We can write it as a pair like 2 , 5, which means "from 2 to 5". Sometimes you are given a whole list of these ranges, and some of them overlap each other. Two ranges overlap when they share at least one point — for example 1 , 4 and 2 , 5 both cover the spot at 2, 3, and 4, so they touch.

The task in the interval merging pattern is this: take a list of ranges and squeeze every group of overlapping ranges into one bigger range that covers all of them.

For example, starting from this list:

2 , 5    6 , 9    5 , 7    1 , 4

the merged answer is:

1 , 5    5 , 9

The first three of the original ranges all chain together into 1 , 5, and the last two chain into 5 , 9. You could solve this with brute force by comparing every range against every other range using nested loops, but that is slow and messy. There is a much cleaner way called the line sweep technique, which finishes the job in a single pass.

The big idea: line sweep

Imagine drawing each range as a line segment on a number line (the x-axis). Now picture moving a vertical "sweep line" from left to right across the number line. As the sweep line passes over the segments, you keep growing the current merged range whenever the next segment still touches it, and you start a fresh merged range when you reach a gap. That single left-to-right walk is the whole trick.

Step 1 — Sort by start

Before sweeping, we must put the ranges in order. We sort the list so the start values go from small to large (non-decreasing order). If two ranges have the same start, we break the tie by their end values.

Sorting matters because the sweep only works if we meet the ranges from left to right. After sorting, the example list becomes:

1 , 4    2 , 5    5 , 7    6 , 9

Step 2 — Start the merged list

We make a second list called merged to hold the final answer. We copy the first sorted range into it as a starting point. So merged begins as:

1 , 4

The last range in merged is the one we are currently "growing". Every new range we look at will be compared against this last range.

Step 3 — Sweep through the rest

Now we walk through the sorted list starting from index 1 (the second range), and for each one we ask a simple question:

Does this new range touch the last range in merged?

The new range touches if its start is less than or equal to the end of the last merged range. In plain words: if the new range begins before (or right at) where the current merged range ends, they overlap.

• If they overlap: we *expand* the last merged range. We set its end to the larger of the two ends. We do not add a new entry — we just stretch the one we already have.
• If they do not overlap: there is a gap. The current merged range is finished, so we *append* the new range to merged as a brand-new last range, and we start growing that one instead.

We keep doing this until we reach the end of the list. Whatever is left in merged is the answer.

Walking through the example

Sorted list: 1 , 4 | 2 , 5 | 5 , 7 | 6 , 9. Start with merged = [1 , 4].

1. Look at 2 , 5. Its start 2 is ≤ the merged end 4, so they overlap. The larger end is 5, so we stretch the merged range to 1 , 5.
2. Look at 5 , 7. Its start 5 compared to the merged end 5 — here the end of one range and the start of the next exactly touch. (More on this edge case below.) In this lesson we treat it as *not* overlapping in this step, so we append 5 , 7. Now merged = [1 , 5] , [5 , 7].
3. Look at 6 , 9. Its start 6 is ≤ the last merged end 7, so they overlap. The larger end is 9, so we stretch the last range to 5 , 9.

We have reached the end. The final answer is:

1 , 5    5 , 9

The boundary (touching) case

What about when one range *ends* exactly where another range *starts*, like 4 , 5 and 5 , 7? Whether that counts as an overlap depends on the problem. Some problems say touching endpoints count as overlapping; others say they do not. In the code, this choice is just one symbol:

• Use <= if a touching point should merge.
• Use < if a touching point should not merge.

Always check what the problem you are solving expects.

The algorithm in short

1. Sort arr by the start coordinate.
2. Create merged and put the first sorted interval in it.
3. For each interval from index 1 onward:

• 3.1 If its start lies within the last merged interval, set that interval's end to the larger of the two ends.
• 3.2 Otherwise, append the interval to merged.

The code (C++)

#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> mergeOverlapping(vector<vector<int>> &arr) {
        // Sort arr by start time
        sort(arr.begin(), arr.end());

        // Initialize output vector and push the first interval
        vector<vector<int>> merged = {arr[0]};

        // Loop through arr and merge if overlapping or adjacent
        for (int i = 1; i < arr.size(); i++) {
            // If the current interval overlaps with the last interval in
            // the merged list, merge them
            // Change '<=' to '<' for cases where the start of an interval
            // coinciding with the end of another is not considered an overlap
            if (arr[i][0] <= merged.back()[1]) {
                // ...stretch the end of the last merged interval...
            }
        }
    }
};

sort(arr.begin(), arr.end()) orders the pairs by their first value automatically. merged.back() is the last interval in merged — the one we are currently growing. arr[i][0] is the start of the interval we are looking at, and the <= check is exactly the "do they touch?" test.

How fast and how much memory

• Time: The sorting step costs O(N log N), where N is the number of intervals. After sorting, we only walk through the list once, which is O(N). The sort dominates, so the overall time is O(N log N) in every case.
• Space: We use an extra merged list.
• *Best case* — everything overlaps into one interval, so merged holds just one entry: O(1) extra space.
• *Worst case* — nothing overlaps, so merged ends up the same size as the input: O(N) extra space.