Day 36 贪心算法

差点就自己写出来了

class Solution {static bool cmp(const vector<int> &a, const vector<int> &b){if (a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];}public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);int result = 0;for (int i = 1; i < intervals.size(); i++){if (intervals[i][0] < intervals[i - 1][1]) // 重叠{result++;intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 注意这里要设置min，否则直接intervals[i][1] = intervals[i - 1][1]也会有问题}}return result;}
};

思路是能想到，但是实现起来就没那么得心应手了

使用哈希表来记录字母最后一次出现的位置还是比较巧妙的。

class Solution {
public:vector<int> partitionLabels(string s) {int table[26] = {0};for (int i = 0; i < s.size(); i++){table[s[i] - 'a'] = i;}int left = 0, right = 0;vector<int> rst;for (int i = 0; i < s.size(); i++){right = max(right, table[s[i] - 'a']);if (i == right){rst.push_back(right - left + 1);left = right + 1;}}return rst;}
};

有了前面的经验，这道题终于是自己解决了。

class Solution {static bool cmp(const vector<int> &a, const vector<int> &b){if (a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];}public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);vector<vector<int>> rst;int left = intervals[0][0], right = intervals[0][1];for (int i = 1; i < intervals.size(); i++){if (intervals[i][0] <= right) // 重叠{right = max(right, intervals[i][1]);}else{rst.push_back({left, right});left = intervals[i][0];right = intervals[i][1];}}rst.push_back({left, right});return rst;}
};