移除最小数目的区间,使得剩余区间互不重叠。
想清楚这道题和计算最小重叠区间的个数的关系,就大概明白了。
1. 如果某一堆区间存在最小交集区间,说明这堆区间最多保留一个区间,其余都要移除。
2. 假如存在另一堆区间,这堆区间有着与上一堆区间不同的最小区间,是否可以证明这两堆区间最终要移除至只剩两个区间?可以证明,因为如果有第三个剩余区间,那么这个区间要么和其中一个重叠,要么和另一个重叠;剩余的这两个区间有没有可能重叠?为啥不能剩余一个区间?假如有两堆各自有最小公共区间的区间,如果只剩余一个区间a,那么这个区间是有可能与两个最小公共区间重叠的,但是,一定可以找到另外两个区间b,c,其中,b,c和a的公共区间不同。否则如果找不到,则与前提不同,即存在两个拥有不同最小公共区间的区间堆。因为要移除最少数量,所以,只能是两堆中剩余两个。
3. 所以,使得剩余区间互不重叠的最小移除数目,是区间总数 - 最小重叠区间个数。
class Solution {
static bool cmp(vector<int>& a, vector<int>& b) {
if (a[0] != b[0]) return a[0] < b[0];
else return a[1] < b[1];
}
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
vector<int> region(2, 0);
int sum = 1;
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
} else sum++;
}
return intervals.size() - sum;
}
};
记录每个字母的第一次出现时的坐标,和最后一次出现时的坐标。然后根据起始坐标从大到小排列,如果起始坐标相等,按照末尾坐标从大到小排列后,遍历区间,依次吞并可以吞并的区间。
这里要注意,有很多没出现过的字母,一直处于[0, 0],需要排除。很麻烦。
class Solution {
static bool cmp(vector<int>& a, vector<int>& b) {
if (a[0] != b[0]) return a[0] < b[0];
else return a[1] < b[1];
}
public:
vector<int> partitionLabels(string s) {
vector<vector<int>> word(26, vector<int>(2, 0));
vector<int> result;
for (int i = 0; i < s.size(); i++) {
if (word[s[i] - 'a'][0] == 0 && word[s[i] - 'a'][1] == 0) {
word[s[i] - 'a'][0] = i;
word[s[i] - 'a'][1] = i + 1;
} else {
word[s[i] - 'a'][1] = i + 1;
}
}
sort(word.begin(), word.end(), cmp);
vector<int> region = word[0];
for (int i = 0; i < 26; i++) {
if (word[i][0] == 0 && word[i][1] == 0) continue;
else if (region[0] == 0 && region[1] == 0) {
region = word[i];
continue;
}
if (word[i][0] >= region[1]) {
result.push_back(region[1] - region[0]);
region = word[i];
} else region[1] = max(region[1], word[i][1]);
}
result.push_back(region[1] - region[0]);
return result;
}
};
巧妙方法:
因为是合并区间的问题,所以可以这么简单。
class Solution {
public:
vector<int> partitionLabels(string s) {
int hash[26] = {0};
for (int i = 0; i < s.size(); i++) {
hash[s[i] - 'a'] = i;
}
int left = 0;
int right = hash[s[0] - 'a'];
vector<int> result;
for (int i = 0; i < s.size(); i++) {
if (right == i) {
result.push_back(right - left + 1);
if (i != s.size() - 1) {
left = i + 1;
right = hash[s[i + 1] - 'a'];
}
} else right = max(hash[s[i] - 'a'], right);
}
return result;
}
};
这就跟上一个的复杂解法类似了。
class Solution {
static bool cmp(vector<int>& a, vector<int>& b) {
if (a[0] != b[0]) return a[0] < b[0];
else return a[1] < b[1];
}
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
vector<int> region = intervals[0];
vector<vector<int>> results;
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] > region[1]) {
results.push_back(region);
region = intervals[i];
} else region[1] = max(intervals[i][1], region[1]);
}
results.push_back(region);
return results;
}
};