题目:435. 无重叠区间
文章链接:代码随想录
视频链接:LeetCode:435.无重叠区间
题目链接:力扣题目链接
图释:
class Solution {
public:static bool cmp(const vector<int>&a, const vector<int>&b){return a[0] < b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {// if(intervals.size() == 0 ||intervals.size() ==1) return 0;sort(intervals.begin(), intervals.end(),cmp);int result = 0;for(int i=1; i<intervals.size(); i++){if(intervals[i-1][1]>intervals[i][0]){result++;intervals[i][1] = min(intervals[i-1][1], intervals[i][1]);}}return result;}
};
题目:763.划分字母区间
文章链接:代码随想录
视频链接:LeetCode:763.划分字母区间
题目链接:力扣题目链接
图释:
class Solution {
public:vector<int> partitionLabels(string s) {int hash[27]={0};for(int i=0; i<s.size(); i++){// s[i]-'a' ask||码,对应下标hash[s[i]-'a'] = i; // 反复更新最远距离 }vector<int> result;int left = 0, right = 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. 合并区间
文章链接:代码随想录
视频链接:LeetCode:56.合并区间
题目链接:力扣题目链接
图释:
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) {if(intervals.size()<=1) return intervals;vector<vector<int>> result;vector<int> path;sort(intervals.begin(), intervals.end(), cmp);path.push_back(intervals[0][0]);for(int i=1; i<intervals.size(); i++){if(intervals[i-1][1] >= intervals[i][0]){// 更新右边边界intervals[i][1] = max(intervals[i][1], intervals[i-1][1]);}else{//没有重叠path.push_back(intervals[i-1][1]);result.push_back(path);path.clear();path.push_back(intervals[i][0]);}}path.push_back(intervals[intervals.size()-1][1]);result.push_back(path);return result;}
};