https://leetcode.cn/problems/non-overlapping-intervals/
算法思想：
求重疊區(qū)間的個數。按照左邊界進行排序，使用當前區(qū)間的左邊界和上一個區(qū)間的右邊界比較，小于則有重疊，傾向于刪除右邊界長的那個區(qū)間，因此將當前區(qū)間的邊界更新為兩個右邊界中的最小那個。
class Solution {
public:
? ? static bool cmp(const vector<int>& a, vector<int>& b)
? ? {
? ? ? ? if(a[0]==b[0])
? ? ? ? ? ? return a[1]<b[1];
? ? ? ? return a[0]<b[0];
? ? }
? ? int eraseOverlapIntervals(vector<vector<int>>& intervals) {
? ? ? ? sort(intervals.begin(), intervals.end(), cmp);
? ? ? ? int count=0;
? ? ? ? cout<<"["<<intervals[0][0]<<", "<<intervals[0][1]<<"] ";
? ? ? ? for(int i=1;i<intervals.size();i++)
? ? ? ? {
? ? ? ? ? ? // cout<<"["<<intervals[i][0]<<", "<<intervals[i][1]<<"] ";
? ? ? ? ? ? if(intervals[i][0]<intervals[i-1][1]) //如果和上一個區(qū)間有交集
? ? ? ? ? ? {?
? ? ? ? ? ? ? ? // cout<<"intervals[i][0]:"<<intervals[i][0]<<" intervals[i-1][1]"<<intervals[i-1][1]<<endl;
? ? ? ? ? ? ? ? intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return count;
? ? }
};
https://leetcode.cn/problems/partition-labels/
算法思想：
求每個字母的最遠下標，當遍歷到的位置=最遠下標時，表示可以截斷了。
class Solution {
public:
? ? vector<int> partitionLabels(string s) {
? ? ? ? //使用一個哈希表記錄每個元素的最遠距離下標
? ? ? ? vector<int> haxi(26,-1);
? ? ? ? for(int i=0;i<s.size();i++)
? ? ? ? {
? ? ? ? ? ? haxi[s[i]-'a'] = i;
? ? ? ? }
? ? ? ? // for(int i=0;i<26;i++)
? ? ? ? //? ? cout<<haxi[i]<<" ";
? ? ? ? // cout<<endl;
? ? ? ? int left = 0;
? ? ? ? int right = 0;
? ? ? ? vector<int> result;
? ? ? ? for(int i=0;i<s.size();i++)
? ? ? ? {
? ? ? ? ? ? right = max(right, haxi[s[i]-'a']);
? ? ? ? ? ? // cout<<s[i]<<" right:"<<right<<" i:"<<i<<" haxi[i]"<<haxi[i]<<endl;
? ? ? ? ? ? if(i==right)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? result.push_back(right-left+1);
? ? ? ? ? ? ? ? left = i+1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return result;
? ? }
};
https://leetcode.cn/problems/merge-intervals/
算法思想：
合并區(qū)間，當出現重合的時候，把上一個區(qū)間和當前區(qū)間合并，合并為左邊界取兩者最小值，右邊界取兩者最大值。當區(qū)間不重合時，把上一個區(qū)間放入結果中。
class Solution {
public:
? ? static bool cmp(const vector<int>& a, const vector<int>& b)
? ? {
? ? ? ? if(a[0]==b[0])
? ? ? ? ? ? return a[1]<b[1];
? ? ? ? return a[0]<b[0];
? ? }
? ? vector<vector<int>> merge(vector<vector<int>>& intervals) {
? ? ? ? sort(intervals.begin(), intervals.end(), cmp);
? ? ? ? // intervals.push_back(vector<int> {INT_MAX-1, INT_MAX});
? ? ? ? vector<vector<int>> result;
? ? ? ? for(int i=1;i<intervals.size();i++)
? ? ? ? {
? ? ? ? ? ? if(intervals[i][0]<=intervals[i-1][1])// 說明有重疊
? ? ? ? ? ? {
? ? ? ? ? ? ? ? intervals[i][0] = min(intervals[i-1][0], intervals[i][0]);
? ? ? ? ? ? ? ? intervals[i][1] = max(intervals[i-1][1], intervals[i][1]);
? ? ? ? ? ? }
? ? ? ? ? ? else //說明不重疊了
? ? ? ? ? ? {
? ? ? ? ? ? ? ? result.push_back(vector<int> {intervals[i-1][0], intervals[i-1][1]});
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? result.push_back(vector<int> {intervals[intervals.size()-1][0], intervals[intervals.size()-1][1]});
? ? ? ? return result;
? ? }
};
