Merge Intervals

How it works

We want to merge all overlapping intervals so the result contains only non-overlapping ranges.

This solution uses a greedy idea with an auxiliary array:

• For every possible start point start, we record the farthest end of any interval that begins at start
• Then we scan from left to right, maintaining the farthest point we must still cover (have)

While scanning:

• if we see an interval starting at position i, we may need to extend our current merged interval’s end to include it
• once our scan index reaches the farthest required end, we can safely close the current merged interval

So the scan behaves like:

• “start a merged interval when we first see coverage”
• “keep extending its end while overlaps exist”
• “close it when we finish the coverage”

Steps

1. Find the maximum start value among all intervals (max_val).
2. Create an array mp of size max_val + 1:
   • mp[start] will store the farthest (end + 1) among intervals that start at start
3. For each interval [start, end]:
   • update mp[start] = max(mp[start], end + 1)
4. Initialize:
   • res as an empty list for merged intervals
   • interval_start = -1 to mark the start of the current merged interval
   • have = -1 to track the farthest end of the current merged interval
5. Scan i from 0 to len(mp) - 1:
   • If mp[i] != 0, it means some interval starts at i:
     • if we are not already in a merged interval, set interval_start = i
     • update have = max(have, mp[i] - 1) (convert back to real end)
   • If have == i, it means we reached the end of the current merged interval:
     • append [interval_start, have] to res
     • reset interval_start and have
6. After the scan, if a merged interval is still open, append it to res.
7. Return res.

Complexity

• Time complexity: O(n + m)
• Space complexity: O(n)

Where n is the length of the array and m is the maximum start value among all the intervals.

Things to watch for

Using Strict Inequality for Overlap Check

Two intervals overlap when current.start <= last.end, not <. Intervals [1, 3] and [3, 5] are considered overlapping and should merge to [1, 5].

Forgetting to Update the End When Merging

When merging overlapping intervals, the new end should be max(last.end, current.end), not just current.end. An earlier interval might extend further than a later-starting one.

Not Sorting Before Processing

The sorting approach assumes intervals are processed in order of start time. Without sorting, you cannot guarantee that overlapping intervals are adjacent, leading to missed merges.

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        max_val = max(interval[0] for interval in intervals)

        mp = [0] * (max_val + 1)
        for start, end in intervals:
            mp[start] = max(end + 1, mp[start])

        res = []
        have = -1
        interval_start = -1
        for i in range(len(mp)):
            if mp[i] != 0:
                if interval_start == -1:
                    interval_start = i
                have = max(mp[i] - 1, have)
            if have == i:
                res.append([interval_start, have])
                have = -1
                interval_start = -1

        if interval_start != -1:
            res.append([interval_start, have])

        return res

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int max_val = 0;
        for (const auto& interval : intervals) {
            max_val = max(interval[0], max_val);
        }

        vector<int> mp(max_val + 1, 0);
        for (const auto& interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            mp[start] = max(end + 1, mp[start]);
        }

        vector<vector<int>> res;
        int have = -1;
        int intervalStart = -1;
        for (int i = 0; i < mp.size(); i++) {
            if (mp[i] != 0) {
                if (intervalStart == -1) intervalStart = i;
                have = max(mp[i] - 1, have);
            }
            if (have == i) {
                res.push_back({intervalStart, have});
                have = -1;
                intervalStart = -1;
            }
        }

        if (intervalStart != -1) {
            res.push_back({intervalStart, have});
        }

        return res;
    }
};