56. Merge Intervals - Explanation

Description

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

You may return the answer in any order.

Note: Intervals are non-overlapping if they have no common point. For example, [1, 2] and [3, 4] are non-overlapping, but [1, 2] and [2, 3] are overlapping.

Example 1:

Input: intervals = [[1,3],[1,5],[6,7]]

Output: [[1,5],[6,7]]

Example 2:

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

Output: [[1,3]]

Constraints:

1 <= intervals.length <= 1000
intervals[i].length == 2
0 <= start <= end <= 1000

Topics

Array Sorting

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(nlogn) time and O(n) space, where n is the size of the input array.

Hint 1

Sorting the given intervals in ascending order based on their start values is beneficial, as it helps in identifying overlapping intervals efficiently. How can you determine if two intervals overlap?

Hint 2

If two intervals are sorted in ascending order by their start values, they overlap if the start value of the second interval is less than or equal to the end value of the first interval.

Hint 3

We iterate through the sorted intervals from left to right, starting with the first interval in the output list. From the second interval onward, we compare each interval with the last appended interval. Can you determine the possible cases for this comparison?

Hint 4

The two cases are: if the current interval overlaps with the last appended interval, we update its end value to the maximum of both intervals' end values and continue. Otherwise, we append the current interval and proceed.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Required to process intervals in order by start time for efficient merging
Intervals - Understanding how to represent, compare, and merge overlapping ranges
Sweep Line Algorithm - Alternative approach that tracks active intervals using events on a timeline

1. Sorting

Intuition

We are given a list of intervals, and some of them may overlap.
The goal is to merge all overlapping intervals so that the final list contains only non-overlapping intervals, covering the same ranges.

A natural way to approach this is:

if intervals are processed in sorted order by start time, then
any overlap can only happen with the most recently added interval

So after sorting:

we keep track of the last merged interval
if the current interval overlaps with it, we merge them
otherwise, we start a new interval

Algorithm

Sort all intervals by their start time.
Initialize the result list output with the first interval.
Iterate through each interval (start, end) in the sorted list:
Let lastEnd be the end of the last interval in output.
If the current interval overlaps with the last one (start <= lastEnd):
- Merge them by updating the end:
  - output[-1][1] = max(lastEnd, end)
Otherwise (no overlap):
- Append the current interval to output as a new interval
After processing all intervals, return output

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda pair: pair[0])
        output = [intervals[0]]

        for start, end in intervals:
            lastEnd = output[-1][1]

            if start <= lastEnd:
                output[-1][1] = max(lastEnd, end)
            else:
                output.append([start, end])
        return output

public class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> output = new ArrayList<>();
        output.add(intervals[0]);

        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            int lastEnd = output.get(output.size() - 1)[1];

            if (start <= lastEnd) {
                output.get(output.size() - 1)[1] = Math.max(lastEnd, end);
            } else {
                output.add(new int[]{start, end});
            }
        }
        return output.toArray(new int[output.size()][]);
    }
}

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> output;
        output.push_back(intervals[0]);

        for (auto& interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            int lastEnd = output.back()[1];

            if (start <= lastEnd) {
                output.back()[1] = max(lastEnd, end);
            } else {
                output.push_back({start, end});
            }
        }
        return output;
    }
};

class Solution {
    /**
     * @param {number[][]} intervals
     * @return {number[][]}
     */
    merge(intervals) {
        intervals.sort((a, b) => a[0] - b[0]);
        const output = [];
        output.push(intervals[0]);

        for (const interval of intervals) {
            const start = interval[0];
            const end = interval[1];
            const lastEnd = output[output.length - 1][1];

            if (start <= lastEnd) {
                output[output.length - 1][1] = Math.max(lastEnd, end);
            } else {
                output.push([start, end]);
            }
        }
        return output;
    }
}

public class Solution {
    public int[][] Merge(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        List<int[]> output = new List<int[]>();
        output.Add(intervals[0]);

        foreach (int[] interval in intervals) {
            int start = interval[0];
            int end = interval[1];
            int lastEnd = output[output.Count - 1][1];

            if (start <= lastEnd) {
                output[output.Count - 1][1] = Math.Max(lastEnd, end);
            } else {
                output.Add(new int[]{start, end});
            }
        }
        return output.ToArray();
    }
}

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    output := [][]int{intervals[0]}

    for _, interval := range intervals[1:] {
        start, end := interval[0], interval[1]
        lastEnd := output[len(output)-1][1]

        if start <= lastEnd {
            output[len(output)-1][1] = max(lastEnd, end)
        } else {
            output = append(output, []int{start, end})
        }
    }
    return output
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        intervals.sortBy { it[0] }
        val output = mutableListOf(intervals[0])

        for (interval in intervals.slice(1 until intervals.size)) {
            val (start, end) = interval
            val lastEnd = output.last()[1]

            if (start <= lastEnd) {
                output[output.size - 1][1] = maxOf(lastEnd, end)
            } else {
                output.add(interval)
            }
        }
        return output.toTypedArray()
    }
}

class Solution {
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        let intervals = intervals.sorted { $0[0] < $1[0] }
        var output: [[Int]] = [intervals[0]]

        for interval in intervals {
            let start = interval[0]
            let end = interval[1]
            var lastEnd = output.last![1]

            if start <= lastEnd {
                output[output.count - 1][1] = max(lastEnd, end)
            } else {
                output.append([start, end])
            }
        }
        return output
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity:
- $O(1)$ or $O(n)$ space depending on the sorting algorithm.
- $O(n)$ for the output list.

2. Sweep Line Algorithm

Intuition

This approach treats each interval as a pair of events on a number line:

an interval starts at start
an interval ends at end

Instead of merging intervals directly, we track how many intervals are currently active as we move from left to right along the number line.

The key idea:

when the number of active intervals goes from 0 → positive, a merged interval starts
when it goes from positive → 0, a merged interval ends

By recording how the count changes at each boundary and sweeping through them in order, we can reconstruct all merged intervals.

Algorithm

Create a map mp to store boundary changes:
- for each interval [start, end]:
  - increment mp[start] (interval starts)
  - decrement mp[end] (interval ends)
Initialize:
- have = 0 to track how many intervals are currently active
- interval = [] to build the current merged interval
- res = [] to store the final merged intervals
Iterate through all keys in mp in sorted order:
For each position i:
- If interval is empty, this position may mark the start of a new merged interval:
  - set interval = [i]
- Update the active count:
  - have += mp[i]
- If have == 0:
  - all intervals have closed at this point
  - append i as the end of the current merged interval
  - add interval to res
  - reset interval to empty
After processing all events, return res

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        mp = defaultdict(int)
        for start, end in intervals:
            mp[start] += 1
            mp[end] -= 1

        res = []
        interval = []
        have = 0
        for i in sorted(mp):
            if not interval:
                interval.append(i)
            have += mp[i]
            if have == 0:
                interval.append(i)
                res.append(interval)
                interval = []
        return res

public class Solution {
    public int[][] merge(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();

        for (int[] interval : intervals) {
            map.put(interval[0], map.getOrDefault(interval[0], 0) + 1);
            map.put(interval[1], map.getOrDefault(interval[1], 0) - 1);
        }

        List<int[]> res = new ArrayList<>();
        int have = 0;
        int[] interval = new int[2];

        for (int point : map.keySet()) {
            if (have == 0) interval[0] = point;
            have += map.get(point);
            if (have == 0) {
                interval[1] = point;
                res.add(new int[] {interval[0], interval[1]});
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        map<int, int> mp;
        for (const auto& interval : intervals) {
            mp[interval[0]]++;
            mp[interval[1]]--;
        }

        vector<vector<int>> res;
        vector<int> interval;
        int have = 0;
        for (const auto& [i, count] : mp) {
            if (interval.empty()) {
                interval.push_back(i);
            }
            have += count;
            if (have == 0) {
                interval.push_back(i);
                res.push_back(interval);
                interval.clear();
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[][]} intervals
     * @return {number[][]}
     */
    merge(intervals) {
        const mp = new Map();
        for (const [start, end] of intervals) {
            mp.set(start, (mp.get(start) || 0) + 1);
            mp.set(end, (mp.get(end) || 0) - 1);
        }

        const sortedKeys = Array.from(mp.keys()).sort((a, b) => a - b);
        const res = [];
        let interval = [];
        let have = 0;

        for (const i of sortedKeys) {
            if (interval.length === 0) {
                interval.push(i);
            }
            have += mp.get(i);
            if (have === 0) {
                interval.push(i);
                res.push(interval);
                interval = [];
            }
        }
        return res;
    }
}

public class Solution {
    public int[][] Merge(int[][] intervals) {
        var mp = new SortedDictionary<int, int>();
        foreach (var point in intervals) {
            if (!mp.ContainsKey(point[0])) mp[point[0]] = 0;
            if (!mp.ContainsKey(point[1])) mp[point[1]] = 0;
            mp[point[0]]++;
            mp[point[1]]--;
        }

        var res = new List<int[]>();
        var interval = new int[2];
        int have = 0;
        foreach (var kvp in mp) {
            if (have == 0) interval[0] = kvp.Key;
            have += kvp.Value;
            if (have == 0) {
                interval[1] = kvp.Key;
                res.Add(new int[] { interval[0], interval[1] });
            }
        }
        return res.ToArray();
    }
}

func merge(intervals [][]int) [][]int {
    mp := make(map[int]int)
    for _, interval := range intervals {
        start, end := interval[0], interval[1]
        mp[start]++
        mp[end]--
    }

    res := [][]int{}
    interval := []int{}
    have := 0
    keys := make([]int, 0, len(mp))
    for key := range mp {
        keys = append(keys, key)
    }
    sort.Ints(keys)

    for _, i := range keys {
        if len(interval) == 0 {
            interval = append(interval, i)
        }
        have += mp[i]
        if have == 0 {
            interval = append(interval, i)
            res = append(res, append([]int{}, interval...))
            interval = []int{}
        }
    }
    return res
}

class Solution {
    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        val mp = TreeMap<Int, Int>()
        for (interval in intervals) {
            val (start, end) = interval
            mp[start] = mp.getOrDefault(start, 0) + 1
            mp[end] = mp.getOrDefault(end, 0) - 1
        }

        val res = mutableListOf<IntArray>()
        var interval = mutableListOf<Int>()
        var have = 0

        for (i in mp.keys) {
            if (interval.isEmpty()) {
                interval.add(i)
            }
            have += mp[i]!!
            if (have == 0) {
                interval.add(i)
                res.add(interval.toIntArray())
                interval = mutableListOf()
            }
        }
        return res.toTypedArray()
    }
}

class Solution {
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        var mp = [Int: Int]()

        for interval in intervals {
            let start = interval[0]
            let end = interval[1]
            mp[start, default: 0] += 1
            mp[end, default: 0] -= 1
        }

        var res = [[Int]]()
        var interval = [Int]()
        var have = 0

        for i in mp.keys.sorted() {
            if interval.isEmpty {
                interval.append(i)
            }
            have += mp[i, default: 0]
            if have == 0 {
                interval.append(i)
                res.append(interval)
                interval = []
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Greedy

Intuition

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”

Algorithm

Find the maximum start value among all intervals (max_val).
Create an array mp of size max_val + 1:
- mp[start] will store the farthest (end + 1) among intervals that start at start
For each interval [start, end]:
- update mp[start] = max(mp[start], end + 1)
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
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
After the scan, if a merged interval is still open, append it to res.
Return res.

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

public class Solution {
    public int[][] merge(int[][] intervals) {
        int max = 0;
        for (int i = 0; i < intervals.length; i++) {
            max = Math.max(intervals[i][0], max);
        }

        int[] mp = new int[max + 1];
        for (int i = 0; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            mp[start] = Math.max(end + 1, mp[start]);
        }

        int r = 0;
        int have = -1;
        int intervalStart = -1;
        for (int i = 0; i < mp.length; i++) {
            if (mp[i] != 0) {
                if (intervalStart == -1) intervalStart = i;
                have = Math.max(mp[i] - 1, have);
            }
            if (have == i) {
                intervals[r++] = new int[] { intervalStart, have };
                have = -1;
                intervalStart = -1;
            }
        }

        if (intervalStart != -1) {
            intervals[r++] = new int[] { intervalStart, have };
        }
        if (intervals.length == r) {
            return intervals;
        }

        int[][] res = new int[r][];
        for (int i = 0; i < r; i++) {
            res[i] = intervals[i];
        }

        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;
    }
};

class Solution {
    /**
     * @param {number[][]} intervals
     * @return {number[][]}
     */
    merge(intervals) {
        let max = 0;
        for (let i = 0; i < intervals.length; i++) {
            max = Math.max(intervals[i][0], max);
        }

        let mp = new Array(max + 1).fill(0);
        for (let i = 0; i < intervals.length; i++) {
            let start = intervals[i][0];
            let end = intervals[i][1];
            mp[start] = Math.max(end + 1, mp[start]);
        }

        let res = [];
        let have = -1;
        let intervalStart = -1;
        for (let i = 0; i < mp.length; i++) {
            if (mp[i] !== 0) {
                if (intervalStart === -1) intervalStart = i;
                have = Math.max(mp[i] - 1, have);
            }
            if (have === i) {
                res.push([intervalStart, have]);
                have = -1;
                intervalStart = -1;
            }
        }

        if (intervalStart !== -1) {
            res.push([intervalStart, have]);
        }

        return res;
    }
}

public class Solution {
    public int[][] Merge(int[][] intervals) {
        int max = 0;
        for (int i = 0; i < intervals.Length; i++) {
            max = Math.Max(intervals[i][0], max);
        }

        int[] mp = new int[max + 1];
        for (int i = 0; i < intervals.Length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            mp[start] = Math.Max(end + 1, mp[start]);
        }

        var res = new List<int[]>();
        int have = -1;
        int intervalStart = -1;
        for (int i = 0; i < mp.Length; i++) {
            if (mp[i] != 0) {
                if (intervalStart == -1) intervalStart = i;
                have = Math.Max(mp[i] - 1, have);
            }
            if (have == i) {
                res.Add(new int[] { intervalStart, have });
                have = -1;
                intervalStart = -1;
            }
        }

        if (intervalStart != -1) {
            res.Add(new int[] { intervalStart, have });
        }

        return res.ToArray();
    }
}

func merge(intervals [][]int) [][]int {
    maxVal := math.MinInt
    for _, interval := range intervals {
        maxVal = max(maxVal, interval[0])
    }

    mp := make([]int, maxVal+1)
    for _, interval := range intervals {
        start, end := interval[0], interval[1]
        mp[start] = max(mp[start], end+1)
    }

    res := [][]int{}
    have := -1
    intervalStart := -1
    for i := 0; i < len(mp); i++ {
        if mp[i] != 0 {
            if intervalStart == -1 {
                intervalStart = i
            }
            have = max(mp[i]-1, have)
        }
        if have == i {
            res = append(res, []int{intervalStart, have})
            have = -1
            intervalStart = -1
        }
    }

    if intervalStart != -1 {
        res = append(res, []int{intervalStart, have})
    }

    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        var maxVal = Int.MIN_VALUE
        for (interval in intervals) {
            maxVal = maxOf(maxVal, interval[0])
        }

        val mp = IntArray(maxVal + 1)
        for (interval in intervals) {
            val (start, end) = interval
            mp[start] = maxOf(mp[start], end + 1)
        }

        val res = mutableListOf<IntArray>()
        var have = -1
        var intervalStart = -1
        for (i in mp.indices) {
            if (mp[i] != 0) {
                if (intervalStart == -1) {
                    intervalStart = i
                }
                have = maxOf(mp[i] - 1, have)
            }
            if (have == i) {
                res.add(intArrayOf(intervalStart, have))
                have = -1
                intervalStart = -1
            }
        }

        if (intervalStart != -1) {
            res.add(intArrayOf(intervalStart, have))
        }

        return res.toTypedArray()
    }
}

class Solution {
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        let maxVal = intervals.map { $0[0] }.max() ?? 0
        var mp = [Int](repeating: 0, count: maxVal + 1)
        for interval in intervals {
            let start = interval[0]
            let end = interval[1]
            mp[start] = max(end + 1, mp[start])
        }

        var res = [[Int]]()
        var have = -1
        var intervalStart = -1

        for i in 0..<mp.count {
            if mp[i] != 0 {
                if intervalStart == -1 {
                    intervalStart = i
                }
                have = max(mp[i] - 1, have)
            }
            if have == i {
                res.append([intervalStart, have])
                have = -1
                intervalStart = -1
            }
        }

        if intervalStart != -1 {
            res.append([intervalStart, have])
        }

        return res
    }
}

Time & Space 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.

Common Pitfalls

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.