# LeeCode 435. 无重叠区间

435. 无重叠区间 - 力扣（LeetCode）

``````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 (end <= intervals[i][0]) {
end = intervals[i][1];
count++;
}
}
return intervals.size() - count;
}
};``````

``````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) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int count = 0;
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]);
count++;
}
}
return count;
}
};``````

# LeeCode 763.划分字母区间

763. 划分字母区间 - 力扣（LeetCode）

``````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 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;
}
};``````

``````class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a[0] < b[0];
}
vector<vector<int>> countLabels(string s) {
vector<vector<int>> hash(26, vector<int>(2,INT_MIN));
vector<vector<int>> hash_filter;
for (int i = 0; i < s.size(); i++) {
if (hash[s[i] - 'a'][0] == INT_MIN)  hash[s[i] - 'a'][0] = i;
hash[s[i] - 'a'][1] = i;
}
for (int i = 0; i < hash.size(); i++) {
if (hash[i][0] != INT_MIN)  hash_filter.push_back(hash[i]);

}
return hash_filter;
}
vector<int> partitionLabels(string s) {
vector<int> res;
vector<vector<int>> hash = countLabels(s);
sort(hash.begin(), hash.end(), cmp);
int rightBoard = hash[0][1];
int leftBoard = 0;
for (int i = 1; i < hash.size(); i++) {
if (hash[i][0] > rightBoard) {
res.push_back(rightBoard - leftBoard + 1);
leftBoard = hash[i][0];
}
rightBoard = max(rightBoard, hash[i][1]);
}
res.push_back(rightBoard - leftBoard + 1);
return res;
}
};``````

# LeeCode 56. 合并区间

56. 合并区间 - 力扣（LeetCode）

``````class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if (intervals.size() == 0) return result;
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
result.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (result.back()[1] >= intervals[i][0]) result.back()[1] = max(result.back()[1], intervals[i][1]);
else result.push_back(intervals[i]);
}
return result;
}
};``````

THE END