57. Insert Interval Medium

1/**
2 * [57] Insert Interval
3 *
4 * You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the i^th interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
5 * Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
6 * Return intervals after the insertion.
7 *  
8 * Example 1:
9 *
10 * Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
11 * Output: [[1,5],[6,9]]
12 *
13 * Example 2:
14 *
15 * Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
16 * Output: [[1,2],[3,10],[12,16]]
17 * Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
18 *
19 *  
20 * Constraints:
21 *
22 * 0 <= intervals.length <= 10^4
23 * intervals[i].length == 2
24 * 0 <= starti <= endi <= 10^5
25 * intervals is sorted by starti in ascending order.
26 * newInterval.length == 2
27 * 0 <= start <= end <= 10^5
28 *
29 */
30pub struct Solution {}
31
32// problem: https://leetcode.com/problems/insert-interval/
33// discuss: https://leetcode.com/problems/insert-interval/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36use std::cmp;
37impl Solution {
38    pub fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {
39        let mut result = vec![];
40        let mut i = 0;
41        while i < intervals.len() && intervals[i][1] < new_interval[0] {
42            result.push(vec![intervals[i][0], intervals[i][1]]);
43            i += 1;
44        }
45        let mut n = new_interval.clone();
46        while i < intervals.len() && intervals[i][0] <= new_interval[1] {
47            n = vec![
48                cmp::min(n[0], intervals[i][0]),
49                cmp::max(n[1], intervals[i][1]),
50            ];
51            i += 1;
52        }
53        result.push(n);
54        while i < intervals.len() {
55            result.push(vec![intervals[i][0], intervals[i][1]]);
56            i += 1;
57        }
58
59        result
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_57() {
71        let result = Solution::insert(
72            vec![
73                vec![1, 2],
74                vec![3, 5],
75                vec![6, 7],
76                vec![8, 10],
77                vec![12, 16],
78            ],
79            vec![4, 8],
80        );
81        assert_eq!(
82            result,
83            vec![vec![1, 2], vec![3, 10], vec![12, 16]]
84        );
85    }
86
87    #[test]
88    fn test_57_2() {
89        let result = Solution::insert(
90            vec![
91                vec![1, 2],
92                vec![3, 5],
93                vec![6, 7],
94                vec![8, 10],
95                vec![12, 16],
96            ],
97            vec![4, 8],
98        );
99        assert_eq!(result, vec![vec![1, 2], vec![3, 10], vec![12, 16]]);
100    }
101}
102