56. Merge Intervals

Description of Problem

Given an array of intervals where intervals[i] = [starti, endi], 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.

Constraints:

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

Solution

Tags: Stack

Explanation

We use the same manner in 452. Minimum Number of Arrows to Burst Balloons. In this case, we do not do intersection. Instead, we do union if there is an overlapping.

Code (Rust)

impl Solution {
    pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut intervals = intervals;
        intervals.sort_by(|a,b| a[0].cmp(&b[0]));

        let mut stack : Vec<(Vec<i32>)> = Vec::new();
        for int in intervals.into_iter() {
            let (c, d) = (int[0], int[1]);
            if let Some(v) = stack.last(){
                let (a, b) = (v[0], v[1]);
                if b >= c {
                    stack.pop();
                    stack.push(vec![a.min(c), b.max(d)]);
                }else{
                    stack.push(int);
                }
            }else{
                stack.push(int);
            }
        }

        return stack;
    }
}

Complexity

n is length of intervals

Time Complexity

\( T(n) = \Theta(n \lg n+ n) \)

Auxiliary Space

\( S(n) = O(n) \)
- For sorting

Leetbook