leetcode56：合并区间

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (const vector<int>& num : nums) {
        cout << "[";
        for (const int& num2 : num) {
            cout << num2 << ",";
        }
        cout << "], ";
    }
    cout << "]" <<endl;
}

/*
    排序后合并
    
    1.将所有区间按照 start 排序，start 相同的按照 end 排序。
    2.从头开始遍历所有区间，求它们的的并集。
    	当前区间为 [start, end]
    	若当前 start 大于前一个区间的 end，则加入到答案数组中，并且更新前一个区间；
    	若当前 start 小于等于前一个区间的 end，则更新前一个区间的 end。

    时间复杂度：O(nlogn)
        其中 n 是区间的数量。
        排序的时间复杂度为 O(nlog⁡n)，排序后遍历区间的时间复杂度为 O(n)。
    空间复杂度：O(n)
        答案数组存储结果列表。
*/
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};

        // 根据每个区间的起始点进行排序
        // sort(intervals.begin(), intervals.end());
        sort(intervals.begin(), intervals.end(),
        [&](const vector<int>& x, const vector<int>& y) {
            if (x[0] != y[0]) return x[0] < y[0];
            return x[1] < y[1];
        });

        vector<vector<int>> res;
        int l = intervals[0][0], r = intervals[0][1];
        for (int i = 1; i < intervals.size(); i ++) {
            if (r < intervals[i][0]) {
                res.push_back({l, r});
                l = intervals[i][0], r = intervals[i][1];
            } else {
                r = max(r, intervals[i][1]);
            }
        }
        // 将最后一个区间添加到结果列表中
        res.push_back({l, r});

        return res;
    }
};

/*
    思路同上，写法略不同
*/
class Solution_1 {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};

        // 根据每个区间的起始点进行排序
        // sort(intervals.begin(), intervals.end());
        sort(intervals.begin(), intervals.end(),
        [&](const vector<int>& x, const vector<int>& y) {
            if (x[0] != y[0]) return x[0] < y[0];
            return x[1] < y[1];
        });

        vector<vector<int>> res;
        for (auto& interval : intervals) {
            if (res.empty() || res.back()[1] < interval[0]) {
                res.push_back(interval);
            } else {
                // 否则，合并区间
                res.back()[1] = max(res.back()[1], interval[1]);
            }
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<vector<int>>> nums = {
        {{1, 3}, {2, 6}, {8, 10}, {15, 18}},
        {{1, 4}, {4, 5}}
    };
    
    for (auto& num : nums) {
        cout << "Input: ";
        printArray(num);
        vector<vector<int>> result = solution.merge(num);
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"sort"
)

/*
    merge 函数内部，首先对区间按照起始位置进行排序。
    然后，遍历排序后的区间，将可以合并的区间合并，并将合并后的区间添加到结果中。
    最后，返回合并后的区间列表。

   时间复杂度：O(nlogn)
       其中 n 是区间的数量。
       排序的时间复杂度为 O(nlog⁡n)，排序后遍历区间的时间复杂度为 O(n)。
*/
func merge(intervals [][]int) [][]int {
    // 按区间的起始位置进行排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    res := [][]int{}
    res = append(res, intervals[0])
    for _, interval := range intervals {
        last := res[len(res) - 1]
        // 若当前区间的起始位置大于前一个区间的结束位置，则添加到结果中
        if len(res) == 0 || last[1] < interval[0] {
            res = append(res, interval)
        } else {
            // 否则，合并当前区间和前一个区间
            last[1] = max(last[1], interval[1])
        }
    }

    return res
}

func main() {
    // 测试用例
	testCases := []struct {
		intervals [][]int
		expected  [][]int
	}{
		{[][]int{{1,3}, {2,6}, {8,10}, {15,18}}, [][]int{{1,6}, {8,10}, {15,18}}},
		{[][]int{{1,4}, {4,5}}, [][]int{{1,5}}},
	}

	for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: intervals = %v\n", i+1, tc.intervals)
		result := merge(tc.intervals)
        resultStr := fmt.Sprintf("%v", result)
        expectedStr := fmt.Sprintf("%v", tc.expected)

		if resultStr == expectedStr {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
		}
	}
}