贪心
重叠区间
重叠区间问题通过固定一边，比较另一边
题目
452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
排序后分情况讨论 1 区间左边界大于上一个的边界，说明还需要一个弓箭 2 比较右边界情况更新最小有边界与下一个区间左边界比较，更新右边界
static bool Cmp(std::vector<int>& a, std::vector<int>&b) {return a[0] < b[0]; // 小到大排序
}int findMinArrowShots(vector<vector<int>>& points) {// 边界判断if (points.size() == 0) return 0;// 按照左边界排序std::sort(points.begin(), points.end(), Cmp);// 不为空至少要一个箭int res = 1;// 比较当前与前一个区间for (int i = 1; i < points.size(); ++i) {if (points[i][0] > points[i-1][1]) res++;// 更新最小右边界作为射入点 贪在气球边缘射入else points[i][1] = std::min(points[i][1], points[i-1][1]);}return res;
}
435. 无重叠区间 - 力扣（LeetCode）
类似于上一道题，列出情况分析，采用左边或右边排序，可以使用上面一题代码取反即可
static bool Cmp(std::vector<int>& a, std::vector<int>& b) {return a[0] < b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;// 排序std::sort(intervals.begin(), intervals.end(), Cmp);// 统计结果int res = 0;// 分割点int end = intervals[0][1];for (int i = 1; i < intervals.size(); ++i) {if (intervals[i][0] >= end) end = intervals[i][1];else {end = std::min(intervals[i][1], end);res++;}}return res;
}
763. 划分字母区间 - 力扣（LeetCode）
统计每个字母最远位置，通过手动构造哈希数组实现
vector<int> partitionLabels(string s) {// 统计最远字符int hash[27] = {0};for (int i = 0; i < s.size(); ++i) {// 统计当前最远的词hash[s[i] - 'a'] = i;}// 统计区间std::vector<int> res;int left = 0, right = 0;for (int i = 0; i < s.size(); ++i) {// 统计最远右端right = std::max(right, hash[s[i] - 'a']);if (i == right) {res.push_back(right - left + 1);left = right + 1;}}return res;
}