LC56 挖掘更优雅的实现

先看题目：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

解法1

fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    if intervals.is_empty() {
        return vec![];
    }
    // 为了方便，先排序
    intervals = intervals.sort_by(|a,b|a[0].cmp(&b[0]));

    let mut result = vec![intervals[0].clone()];

    for i in 1..intervals.len() {
        let current = &intervals[i];

        let last = result.last_mut().unwrap();

        if current[0] <= last[1] {
            // 重叠，合并区间
            last[1] = last[1].max(current[1]); 
            //利用max(),减少一次条件的判断
        } else {
            // 不重叠，添加新区间
            result.push(current.clone());
        }
    }
}

解法2

不用for循环，使用迭代器

思想：排序后，当前cur，看后面的区间是否有重合部分，有的话修改cur[1]，没有的话再去push进res

fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    if intervals.is_empty() {
        return vec![];
    }
    // 为了方便，先排序
    intervals.sort_by_key(|interval| interval[0]);

    let mut result = vec![];
    let mut current = intervals[0].clone();

    for interval in intervals.into_iter().skip(1) {
        if interval[0] <= current[1] {
            current[1] = current[1].max(interval[1]);
        } else {
            result.push(current);
            current = interval;
        }
    }
    // 把最后一个区间加上去
    result.push(current);
    result
}

解法3

使用reduce

pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    if intervals.is_empty() {
        return vec![];
    }
    // 排序
    intervals.sort_by_key(|i| i[0]);
    // 取第一个区间
    let first = intervals.remove(0);
    intervals.into_iter().fold(vec![first], |mut acc, int| {
        let last = acc.last_mut().unwrap();
        if int[0] <= last[1] {
            // 合并区间
            last[1] = last[1].max(int[1]);
        } else {
            // 添加新区间
            acc.push(int);
        }
        acc
    })
}