0056.合并区间

https://leetcode.cn/problems/merge-intervals/

方法一：排序 + 遍历

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	ans := [][]int{intervals[0]}
	for i := 1; i < len(intervals); i++ {
		x, y := intervals[i][0], intervals[i][1]
		if x > ans[len(ans)-1][1] {
			ans = append(ans, []int{x, y})
		} else if y > ans[len(ans)-1][1] {
			ans[len(ans)-1][1] = y
		}
	}
	return ans
}

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 ans = Vec::new();

        for v in intervals {
            if ans.is_empty() {
                ans.push(v);
                continue;
            }
            let last = ans.last_mut().unwrap();
            if v[0] > last[1] {
                ans.push(v);
            } else if v[1] > last[1] {
                last[1] = v[1];
            }
        }
        ans
    }
}