#56

Medium

LeetCode Problem Workspace

Merge Intervals

Merge Intervals requires sorting an array of interval pairs and combining overlaps efficiently using sequential comparison.

array sorting

Problem Statement

Given an array of intervals where each interval is represented as [starti, endi], merge all overlapping intervals and return an array of non-overlapping intervals that covers all original intervals. Intervals may touch or overlap, and the output should combine them to form the minimal number of ranges.

For example, given intervals = [[1,3],[2,6],[8,10],[15,18]], the result should be [[1,6],[8,10],[15,18]] because the first two intervals overlap. Another example: intervals = [[1,4],[4,5]] should return [[1,5]] as overlapping endpoints are merged.

Examples

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Intervals [1,4] and [4,5] are considered overlapping.

Constraints

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

Solution Approach

Sort intervals by start time

Begin by sorting the intervals based on their starting values. This ensures that any overlapping intervals are adjacent, simplifying the merging process.

Iterate and merge overlaps

Initialize an empty list for merged intervals. Traverse the sorted intervals, and if the current interval overlaps with the last interval in the merged list, update the end to the maximum end value. Otherwise, append it as a new interval.

Return consolidated intervals

After processing all intervals, return the merged list. This guarantees all overlapping ranges are combined and non-overlapping intervals remain in order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n) and iterating to merge intervals is O(n), so the overall time complexity is O(n log n). Space complexity is O(n) in the worst case for storing merged intervals.

What Interviewers Usually Probe

Checks if you sort intervals before merging, as failing to sort leads to incorrect merges.
Looks for a clean in-place or linear pass after sorting, showing understanding of array traversal and comparison.
Wants explanation of edge cases where intervals share endpoints or fully overlap.

Common Pitfalls or Variants

Common pitfalls

Failing to sort intervals first, causing incorrect overlap detection.
Not updating the end of merged intervals correctly, leading to incomplete merges.
Ignoring cases where intervals touch but do not strictly overlap, e.g., [1,4] and [4,5].

Follow-up variants

Merge intervals with additional interval insertion, testing dynamic updates to merged lists.
Merge intervals using linked list structure instead of array, emphasizing pointer manipulation.
Count overlapping intervals without merging, focusing on interval coverage rather than consolidation.

FAQ

What is the main idea behind the Merge Intervals problem?

Sort the intervals by start time and sequentially merge overlapping intervals to produce non-overlapping ranges.

Can intervals that touch at endpoints be merged?

Yes, intervals like [1,4] and [4,5] are considered overlapping for merging purposes.

What is the time complexity for the Merge Intervals solution?

Sorting takes O(n log n) and merging takes O(n), so the total is O(n log n).

How does the array plus sorting pattern apply here?

Sorting ensures overlaps are adjacent, and linear scanning merges intervals efficiently, showcasing array plus sorting pattern usage.

What common mistakes should I avoid when merging intervals?

Do not skip sorting, fail to update merged ends, or ignore intervals that only touch at endpoints.

terminal

Solution

Solution 1: Sorting + One-pass Traversal

We can sort the intervals in ascending order by the left endpoint, and then traverse the intervals for merging operations.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []
        st, ed = intervals[0]
        for s, e in intervals[1:]:
            if ed < s:
                ans.append([st, ed])
                st, ed = s, e
            else:
                ed = max(ed, e)
        ans.append([st, ed])
        return ans

JavaScript

/**

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []
        st, ed = intervals[0]
        for s, e in intervals[1:]:
            if ed < s:
                ans.append([st, ed])
                st, ed = s, e
            else:
                ed = max(ed, e)
        ans.append([st, ed])
        return ans

Solution 2

#### Python3

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []
        st, ed = intervals[0]
        for s, e in intervals[1:]:
            if ed < s:
                ans.append([st, ed])
                st, ed = s, e
            else:
                ed = max(ed, e)
        ans.append([st, ed])
        return ans

Solution 3

#### TypeScript

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []
        st, ed = intervals[0]
        for s, e in intervals[1:]:
            if ed < s:
                ans.append([st, ed])
                st, ed = s, e
            else:
                ed = max(ed, e)
        ans.append([st, ed])
        return ans

Continue Practicing

#49 group anagrams #47 permutations ii #75 sort colors