https://leetcode.cn/problems/non-overlapping-intervals/
算法思想：
求重叠区间的个数。按照左边界进行排序，使用当前区间的左边界和上一个区间的右边界比较，小于则有重叠，倾向于删除右边界长的那个区间，因此将当前区间的边界更新为两个右边界中的最小那个。
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]) //如果和上一个区间有交集
{
// 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/
算法思想：
合并区间，当出现重合的时候，把上一个区间和当前区间合并，合并为左边界取两者最小值，右边界取两者最大值。当区间不重合时，把上一个区间放入结果中。
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;
}
};
