Merge Intervals

January 10, 2025

Inserting Intervals: Merging and Maintaining

The task of merging overlapping intervals is a frequent problem in computer science, often encountered in scheduling and timeline management scenarios.

In this article, we’ll explore how to merge intervals and return a concise, non-overlapping set that covers all the given ranges.

Problem Description

You are given an array of intervals where each interval is represented as intervals[i] = [start_i, end_i]. Your task is to merge all overlapping intervals into a single interval whenever possible and return the resulting array.

Key Points:

Overlapping Definition: Two intervals overlap if their ranges have at least one common point.
- For example:
  - [1,2] and [3,4] are non-overlapping.
  - [1,2] and [2,3] overlap, as they share the point 2.
Goal: Minimize the total number of intervals by merging overlapping ones.

Example 1

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

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

Explanation:

[1,3] overlaps with[1,5], so they are merged into [1,5].
[6,7] does not overlap with any other interval, so it remains as is.

Example 2

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

Output: [[1,3]]

Explanation:

[1,2] and [2,3] overlap, so they are merged into [1,3].

Approach to Solve the Problem

To solve this problem effectively, we can use the following approach:

Step 1: Sort the Intervals

Sorting the intervals by their start time ensures that overlapping intervals appear consecutively in the list. This makes it easier to merge them.

Step 2: Merge Overlapping Intervals

Use a result list to store merged intervals.
Compare each interval with the last interval in the result list:
- If they overlap, merge them by updating the end of the last interval to the maximum end time.
- If they don’t overlap, add the current interval to the result list.

Algorithm

Sort the intervals based on their start time.
Initialize an empty list merged to store the result.
Iterate through the sorted intervals:
- If the current interval overlaps with the last merged interval, merge them.
- Otherwise, add the current interval to the result list.

There are mainly three approach to solve this problem –

Sorting
Sweep Line Algorithm
Greedy

1. Sorting

Time complexity:
Space complexity: $O (1)$ or depending on the sorting algorithm.

Python

C++

Java

JavaScript

Python

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

C++

class Solution {
public:
    vector> merge(vector>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector> 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;
    }
};

Java

public class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List 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()][]);
    }
}

JavaScript

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

2. Sweep Line Algorithm

Time & Space Complexity

Time complexity: O(nlog n)
Space complexity:

Code

C++

Java

Python

JavaScript

C++

class Solution {
public:
    vector> insert(vector>& intervals, vector& newInterval) {
        if (intervals.empty()) {
            return {newInterval};
        }

        int n = intervals.size();
        int target = newInterval[0];
        int left = 0, right = n - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (intervals[mid][0] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        intervals.insert(intervals.begin() + left, newInterval);

        vector> res;
        for (const auto& interval : intervals) {
            if (res.empty() || res.back()[1] < interval[0]) {
                res.push_back(interval);
            } else {
                res.back()[1] = max(res.back()[1], interval[1]);
            }
        }

        return res;
    }
};

Java

public class Solution {
    public int[][] merge(int[][] intervals) {
        TreeMap 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 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()][]);
    }
}

Python

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

JavaScript

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

3. Greedy

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

C++

Java

Python

JavaScript

C++

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

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

Java

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

Python

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

JavaScript

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

Unlock this article for Free,
by logging in

Merge Intervals

Inserting Intervals: Merging and Maintaining

Problem Description

Key Points:

Approach to Solve the Problem

Step 1: Sort the Intervals

Step 2: Merge Overlapping Intervals

Algorithm

There are mainly three approach to solve this problem –

1. Sorting

2. Sweep Line Algorithm

Time & Space Complexity

Code

3. Greedy

More Articles

30+ Companies are Hiring

Unlock this article for Free, by logging in

Merge Intervals

Inserting Intervals: Merging and Maintaining

Problem Description

Key Points:

Approach to Solve the Problem

Step 1: Sort the Intervals

Step 2: Merge Overlapping Intervals

Algorithm

There are mainly three approach to solve this problem –

1. Sorting

2. Sweep Line Algorithm

Time & Space Complexity

Code

3. Greedy

More Articles

30+ Companies are Hiring

Unlock this article for Free,
by logging in