0056. 合并区间 Merge Intervals

问题描述

这是一个排序题.

排序

因为给定的区间是无序的, 我们先以每个区间的起始点来对它进行排序, 之后再统计.

步骤如下:

1. 对 intervals 所有区间的起始点进行排序, intervals.sort_by_key(|interval| interval[0])
2. 创建一个动态数组 ans, 用来存储不重叠的区间
3. 遍历 intervals 中的所有数对, 然后合并有重叠的区间, 并将不重叠的区间存储到 ans 数组中
   1. 如果有重叠, 只需要更新区间的终点值即可
   2. 如果没有重叠, 则需要把之间的区间存到 ans 数组, 并同时更新起点和重点
4. 遍历 ans 数组, 统计所有不重叠区间占用的点数

#![allow(unused)]
fn main() {
// Sorting
pub fn merge1(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    debug_assert!(intervals.len() >= 2);
    for interval in &intervals {
        debug_assert!(interval.len() == 2);
    }

    let mut intervals = intervals;
    // 基于起始值来排序.
    intervals.sort_by_key(|interval| interval[0]);

    let mut out = Vec::with_capacity(intervals.len());
    let mut start: i32 = intervals[0][0];
    let mut end: i32 = intervals[0][1];

    for mut interval in intervals {
        let (start1, end1) = (interval[0], interval[1]);
        // 完全没有交叉, 保存上一个值, 并更新 (start, end)
        if start1 > end {
            interval[0] = start;
            interval[1] = end;
            out.push(interval);
            start = start1;
            end = end1;
        } else {
            // 有重叠, 只需要更新 end 的值
            end = end.max(end1);
        }
    }

    // 插入最后一组数值
    out.push(vec![start, end]);
    out
}
}

该算法的时间复杂度是 O(n log(n)), 空间复杂度是 O(n).