Merge Intervals

LeetCode 56 | Difficulty: Medium

Medium

Problem 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.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Example 3:

Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.

Constraints:

- `1 <= intervals.length <= 10^4`

- `intervals[i].length == 2`

- `0 <= start~i~ <= end~i~ <= 10^4`

Topics: Array, Sorting

---

Approach

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 128 ms)

Metric	Value
Runtime	128 ms
Memory	43.6 MB
Date	2021-11-18

Solution

public class Solution {
    public int[][] Merge(int[][] intervals) {
        Array.Sort(intervals, (a,b) => a[0].CompareTo(b[0]));
    List<int[]> output = new List<int[]>();
    int[] currentInterval = intervals[0];
    foreach (var nextInterval in intervals)
    {
        int currentIntervalEnd = currentInterval[1];
        int nextIntervalStart = nextInterval[0];
        int nextIntervalEnd = nextInterval[1];
        
        if(currentIntervalEnd >= nextIntervalStart)
        {
            currentInterval[1] = Math.Max(currentIntervalEnd, nextIntervalEnd);
            
        }
        else
        {
            output.Add(currentInterval);
            currentInterval = nextInterval;
        }
    }
    output.Add(currentInterval);
    return output.ToArray();    
    }
}

📜 1 more C# submission(s)

Submission (2021-12-24) — 132 ms, 43.2 MB

public class Solution {
    public int[][] Merge(int[][] intervals) {
        Array.Sort(intervals, (a,b) => a[0].CompareTo(b[0]));
    List<int[]> output = new List<int[]>();
    int[] currentInterval = intervals[0];
    foreach (var nextInterval in intervals)
    {
        int currentIntervalEnd = currentInterval[1];
        int nextIntervalStart = nextInterval[0];
        int nextIntervalEnd = nextInterval[1];
        
        if(currentIntervalEnd >= nextIntervalStart)
        {
            currentInterval[1] = Math.Max(currentIntervalEnd, nextIntervalEnd);
            
        }
        else
        {
            output.Add(currentInterval);
            currentInterval = nextInterval;
        }
    }
    output.Add(currentInterval);
    return output.ToArray();    
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.