56. Merge Intervals Medium

1/**
2 * [56] Merge Intervals
3 *
4 * 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.
5 *  
6 * Example 1:
7 *
8 * Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
9 * Output: [[1,6],[8,10],[15,18]]
10 * Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
11 *
12 * Example 2:
13 *
14 * Input: intervals = [[1,4],[4,5]]
15 * Output: [[1,5]]
16 * Explanation: Intervals [1,4] and [4,5] are considered overlapping.
17 *
18 *  
19 * Constraints:
20 *
21 * 1 <= intervals.length <= 10^4
22 * intervals[i].length == 2
23 * 0 <= starti <= endi <= 10^4
24 *
25 */
26pub struct Solution {}
27
28// problem: https://leetcode.com/problems/merge-intervals/
29// discuss: https://leetcode.com/problems/merge-intervals/discuss/?currentPage=1&orderBy=most_votes&query=
30
31// submission codes start here
32use std::cmp;
33impl Solution {
34    pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
35        let mut data = intervals.clone();
36        data.sort();
37        let mut result: Vec<Vec<i32>> = vec![];
38
39        for i in data {
40            match result.last() {
41                Some(l) => {
42                    let (overlap, r) = Self::overlap(&i, l);
43                    if overlap {
44                        result.pop();
45                        result.push(r);
46                    } else {
47                        result.push(i);
48                    }
49                }
50                None => {
51                    result.push(i);
52                }
53            }
54        }
55        result
56    }
57
58    fn overlap(a: &Vec<i32>, b: &Vec<i32>) -> (bool, Vec<i32>) {
59        if a[0] > b[0] {
60            return Self::overlap(b, a);
61        }
62        if a[1] >= b[0] {
63            (true, vec![a[0], cmp::max(a[1], b[1])])
64        } else {
65            (false, vec![])
66        }
67    }
68}
69
70// submission codes end
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn test_56() {
78        assert_eq!(
79            Solution::merge(vec![vec![1, 3], vec![2, 6], vec![8, 10], vec![15, 18]]),
80            vec![vec![1, 6], vec![8, 10], vec![15, 18]]
81        );
82    }
83}
84