【算法日志】贪心算法刷题：重叠区问题(day31)

代码随想录刷题60Day

---

目录

前言

无重叠区间（筛选区间）

划分字母区间（切割区间）

 合并区间

---

前言

今日的重点是掌握重叠区问题。

---

无重叠区间（筛选区间）

   int eraseOverlapIntervals(vector<vector<int>>& intervals) {int count = 0;const int size = intervals.size();sort(intervals.begin(), intervals.end());for (int i = 0; i < size; ++i){int right = intervals[i][1];int j;for (j = i + 1; j < size; ++j){if (right > intervals[j][1])right = intervals[j][1];else if (right <= intervals[j][0])break;}i = j - 1;++count;}return size - count;}

划分字母区间（切割区间）

   vector<int> partitionLabels(string s) {vector<int> result;const int size = s.length();int front = 0, back = size - 1;while(front < size){while (s[front] != s[back])--back;if (front < back)for (int i = front + 1; i <= back; ++i){while (s[i] == s[i - 1])++i;if (i > back) break;int j  = size - 1;while (j > back && s[i] != s[j])j--;back = j;}result.push_back(back - front + 1);front = back + 1;back = size - 1;}return result;}

 合并区间

   vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;sort(intervals.begin(), intervals.end());int size = intervals.size();for (int i = 0; i < size; ++i){int j;int right = intervals[i][1];for (j = i + 1; j < size; ++j){if (right < intervals[j][0])break;elseright = max(right, intervals[j][1]);}result.push_back({intervals[i][0], right});i = j - 1;}return result;}