合并區間

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;
}