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) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 1;int end = intervals[0][1];for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] >= end) {end = intervals[i][1];count++;} }return intervals.size() - count;}
};
763.划分字母区间
class Solution {
public:vector<int> partitionLabels(string s) {int hash[27] = {0};for (int i = 0; i < s.size(); i++) {hash[s[i] - 'a'] = i;}vector<int> result;int right = 0;int left = 0;for (int i = 0; i < s.size(); i++) {right = max(right, hash[s[i] - 'a']);if (i == right) {result.push_back(right - left + 1);left = i + 1;}}return result;}
};
56. 合并区间
push进result,然后用result.back()最后这个区间的右边界与下一个区间的左边界比较
class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result;sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) {result.back()[1] = max(intervals[i][1],result.back()[1]);} else {result.push_back(intervals[i]);}}return result;}
};