贪心 Leetcode 56 合并区间

合并区间

Leetcode 56

学习记录自代码随想录

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

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

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

提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

要点：1.排序，sort(intervals.begin(), intervals.end(), [](auto& a, auto& b){return a[0] < b[0];});使用lamda函数，此种排序方式谨记
2.如果前一个区间末尾>=后一个区间开始则将前一个区间末尾值改为前一个区间末尾值和后一个区间末尾值中的较大值；

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;  // 一个结果数组存储输出
        // 排序，使用lamda函数，此种排序方式谨记
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b){return a[0] < b[0];});
        for(int i = 0; i < intervals.size(); i++){
            // 如果前一个区间末尾>=后一个区间开始则将前一个区间末尾值改为前一个区间末尾值和后一个区间末尾值中的较大值
            if(!result.empty() && result[result.size()-1][1] >= intervals[i][0]){
                result[result.size()-1][1] = max(result[result.size()-1][1], intervals[i][1]);
            }else{
                result.push_back(intervals[i]);
            }
        }

        return result;
    }
};

扩展：

#include <vector>
#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct Period {
    int s; // 开始时间
    int e; // 结束时间
};

class ActivityManagerBase {
public:
    virtual vector<Period> getModBusyPeriods(const string& mod) = 0;
    virtual bool addBusyPeriods(const string& mod, const Period& prd) = 0;
};

class ActivityManager : public ActivityManagerBase{
private:
    unordered_map<string, vector<Period>> modPeriods;

    // 辅助函数，用于合并重叠的时段
    vector<Period> mergePeriods(vector<Period>& periods) {
        vector<Period> merged;
        for (const auto& period : periods) {
            if (!merged.empty() && merged.back().e >= period.s) {
                merged.back().e = max(merged.back().e, period.e);
            } else {
                merged.push_back(period);
            }
        }
        return merged;
    }
public:
    vector<Period> getModBusyPeriods(const string& mod) override{
        if(modPeriods.count(mod) == 0){
            return {};
        }
        return mergePeriods(modPeriods[mod]);
    }

    bool addBusyPeriods(const string& mod, const Period& prd) override{
        modPeriods[mod].push_back(prd);
        sort(modPeriods[mod].begin(), modPeriods[mod].end(),
            [](auto& a, auto& b){return a.s < b.s;});
        return true;
    }
};

int main(){
    // 在C++中，抽象类是包含至少一个纯虚函数的类，它不能被实例化。
    // 在这个例子中，ActivityManagerBase 是一个抽象类，
    // 因为它有两个纯虚函数：getModBusyPeriods 和 addBusyPeriods。

    // 应该创建一个派生类（如 ActivityManager），
    // 并在派生类中实现所有的纯虚函数。然后，你可以创建派生类的对象。
    ActivityManager AM;
    vector<string> mods = {"m1", "m2", "m1", "m2"};
    vector<Period> prds = {{2,6}, {8,10}, {1,3}, {15,18}};

    for(int i = 0; i < mods.size(); i++){
        AM.addBusyPeriods(mods[i], prds[i]);
    }

    vector<Period> m1_periods = AM.getModBusyPeriods("m1");
    for(const auto& period : m1_periods){
        cout << '{' << period.s << ',' << period.e << '}';
    }

    return 0;
}