代码随想录算法训练营第三十六天|435. 无重叠区间 763.划分字母区间 56. 合并区间

目录

LeeCode 435. 无重叠区间

LeeCode 763.划分字母区间

LeeCode 56. 合并区间

---

LeeCode 435. 无重叠区间

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

思路1：按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

时间复杂度：O（n log n）       空间复杂度：O（n）

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

思路2：左边界排序，直接求 重叠的区间，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）

思路1：遍历的过程中找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点。

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

思路2：统计字符串中所有字符的起始和结束位置，记录这些区间，将区间按左边界从小到大排序，找到边界将区间划分成组，互不重叠。找到的边界就是答案。

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）

思路：对区间排序后判断是否重合，合并区间：将合并后的左右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

时间复杂度：O（n log n）       空间复杂度：O（log n）

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