摘要
- 重叠区间问题，常常先将区间按左边界或右边界的大小进行排序，约束相邻的区间如何发生重叠，便于使用贪心策略。
LeetCode435 无重叠区间
- 首先题目要求移除最小数量的区间来使剩余区间互不重叠，那直观地来看，应该被移除的区间是那种容易和其他区间重叠的区间：对于区间
越小，
越大，这个区间在数轴上的跨度就越大，就越容易和其他区间重叠。
- 所以当两个区间重叠时，根据上述分析，贪心策略应该是删除跨度较大的那个区间。
- 为了方便比较区间的“跨度”，可以先按
从小到大排序一次区间。这可以保证当两个相邻区间重叠时，只可能是
。
- 从左到右遍历一次排序过的区间，当遇到两个相邻的区间重叠时，根据贪心策略，删除
较大的那个区间，保留
题解代码如下
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] < b[0];
else return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
int count = 0;
int curEnd = INT_MIN;
for (int i = 0; i < intervals.size(); i++) {
if (intervals[i][0] >= curEnd) {
curEnd = intervals[i][1];
}
else {
// 保留 End 较小的区间
curEnd = min(intervals[i][1], curEnd);
// 删除 End 最大的那个区间
count++;
}
}
return count;
}
};
LeetCode763 划分字母区间
- 初见题目的想法，从左到右遍历一次输入字符串
s，记录每个字母最先出现的下标start和最后出现的下标end，作为划分字母区间的依据。
int hash(char letter) {
if (letter < 'a' || letter > 'z') return 26;
return letter - 'a';
}
/* …… */
vector<int> startOf(26 + 1, s.size());
vector<int> endOf(26 + 1, -1);
for (int i = 0; i < s.size(); i++) {
startOf[hash(s[i])] = min(i, startOf[hash(s[i])]);
endOf[hash(s[i])] = max(i, endOf[hash(s[i])]);
}
/* …… */
- 再次从左到右遍历一次字符串，根据之前保存的每个字母的
start和end来划分字母区间。
题解代码如下
class Solution {
public:
int hash(char letter) {
if (letter < 'a' || letter > 'z') return 26;
return letter - 'a';
}
vector<int> partitionLabels(string s) {
vector<int> startOf(26 + 1, s.size());
vector<int> endOf(26 + 1, -1);
for (int i = 0; i < s.size(); i++) {
startOf[hash(s[i])] = min(i, startOf[hash(s[i])]);
endOf[hash(s[i])] = max(i, endOf[hash(s[i])]);
}
vector<int> res;
int start = s.size();
int end = -1;
for (int i = 0; i < s.size(); i++) {
// 记录这个区间以什么字母开始，以及开始的位置
start = min(startOf[hash(s[i])], start);
// 记录这个区间以什么字母结束，以及结束的位置
end = max(endOf[hash(s[i])], end);
// 区间的开始位置和结束位置是动态更新的
if (i == end) {// 当 i 到达结束位置时，保存当前区间
res.push_back(end - start + 1);
// 去划分下一个区间
start = s.size();
}
}
return res;
}
};
- 其实，从左到右遍历字符串，已经代替了
start的作用，因为区间肯定是以第一个字母（无论哪个字母）作为开始位置的，从左到右遍历字符串并不需要一直更新start，只需要更新end即可。（如果从右向左遍历字符串的话，就是更新start而不需要更新end）
class Solution {
public:
int hash(char letter) {
if (letter < 'a' || letter > 'z') return 26;
return letter - 'a';
}
vector<int> partitionLabels(string s) {
vector<int> startOf(26 + 1, s.size());
vector<int> endOf(26 + 1, -1);
for (int i = 0; i < s.size(); i++) {
startOf[hash(s[i])] = min(i, startOf[hash(s[i])]);
endOf[hash(s[i])] = max(i, endOf[hash(s[i])]);
}
vector<int> res;
// int start = s.size();
int start = 0;
int end = -1;
for (int i = 0; i < s.size(); i++) {
// start = min(startOf[hash(s[i])], start);
end = max(endOf[hash(s[i])], end);
if (i == end) {
res.push_back(end - start + 1);
// start = s.size();
start = i + 1;
}
}
return res;
}
};
LeetCode56 合并区间
- 首先将区间按左边界从小到大排序，这可以保证相邻的两个区间发生重叠时，只可能是
。
- 贪心策略：当两个相邻区间重叠时，就合并这两个区间。
题解代码如下
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] < b[0];
else return a[1] < b[1];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> res;
if (intervals.empty()) return res;
vector<int> cur = intervals[0];
for (int i = 1; i < intervals.size(); i++) {
// 当前区间与上一个区间（或合并后的区间）不重叠
if (intervals[i][1] < cur[0] || cur[1] < intervals[i][0]) {
// 将上一个区间放入结果集
res.push_back(cur);
// 将 cur 更新为 intervals[i]
cur = intervals[i];
}
else {// 当前区间与上一个区间重叠
// 合并两个区间，左边界取最小值，右边界取最大值
cur[0] = min(intervals[i][0], cur[0]);
cur[1] = max(intervals[i][1], cur[1]);
}
}
// 不要忘记将最后一个区间放入结果集
res.push_back(cur);
return res;
}
};
