435. 无重叠区间
这道题的确是思路和昨天最后一道题一样，但是我没做昨天最后那道题，虽然看过一遍以为会了，其实没有。今天做了这道题就体现出来了。这道题的思路是会了。
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b){
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
int count = 0;
int line = intervals[0][1];
for(int i=1; i<intervals.size(); i++){
if(line <= intervals[i][0]){
line = intervals[i][1];
}
else{
line = min(line, intervals[i][1]);
count++;
}
}
return count;
}
};
763.划分字母区间
跟着Carl的文字讲解写出来的。自己写的时候根本没思路，而且净是edge case。我自己想的时候没有把有效的元素列出来，所以没能从中找到规律。
class Solution {
public:
vector<int> partitionLabels(string s) {
if(s.length() == 1){
return vector<int>{1};
}
vector<int> result;
vector<int> vlist(26,0);
vector<int> sum_range(s.length());
for(int i=0; i<s.length(); i++){
vlist[s[i]-'a'] = i;
}
for(int i=0; i<s.length(); i++){
sum_range[i] = vlist[s[i]-'a'];
}
int cur_max;
int pre_index = 0;
for(int i=0; i<sum_range.size(); i++){
cur_max = max(sum_range[i],cur_max);
if(i == cur_max){
result.push_back(i-pre_index+1);
pre_index = i+1;
}
}
return result;
}
};
56. 合并区间
跌跌撞撞，但是写出来了！原理其实就是昨天最后一题和今天的第一道题。 但我不是一次性写出来的。我开始的时候以为只对比右层就可以，但是其实需要考虑的是在左侧有序的基础上再给右侧排序。然后在for loop里再一步步更新左右的最大/小值。如果遇到不在该区域的，就把上一个值写到答案里再接着找左右的极值。
class Solution {
public:
static bool cmp(vector<int>& a, 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);
vector<vector<int>> result;
int left_edge = intervals[0][0];
int right_edge = intervals[0][1];
for(int i=1; i<intervals.size(); i++){
if(intervals[i][0] > right_edge){
vector<int> temp = {left_edge,right_edge};
result.push_back(temp);
left_edge = intervals[i][0];
right_edge = intervals[i][1];
}
else{
left_edge = min(left_edge,intervals[i][0]);
right_edge = max(right_edge,intervals[i][1]);
}
}
vector<int> temp = {left_edge,right_edge};
result.push_back(temp);
return result;
}
};
我看了遍Carl的解法。他只是对intervals的左值进行了排序，这样的话，左面就不可能有更小的值了。然后对比右面的值和当前i的左值来看有没有重叠，重叠的话，就把result里的右值取当前两个右值里最大的。如果不重叠，就把当前的i对应的数组值直接放进result。
