435. 无重叠区间

总和 - 不相交的长度

class Solution {
public:
    // 不相交的最大个数
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        int res = 1;
        sort(intervals.begin(), intervals.end(), [](vector<int>& vec1, vector<int>& vec2)
        {
            return vec1[1] < vec2[1];
        });

        int end = intervals[0][1];
        for (int i = 1; i < n; i ++)
        {
            if (intervals[i][0] >= end)
            {
                end = intervals[i][1];
                res ++;
            }
        }
        return n - res;
    }
};

763. 划分字母区间

一个区段里面应该走到的最远的下标

class Solution {
public:
    // 一个范围内的所有的都到达了最远
    vector<int> partitionLabels(string s) {
        vector<int> res;
        unordered_map<int, int> umap;
        int n = s.size();
        for (int i = 0; i < n; i ++)
        {
            umap[s[i]] = i;
        }

        int far = umap[s[0]], begin = 0;
        for (int i = 0; i < n; i ++)
        {
            far = max(far, umap[s[i]]);
            // 区间符合条件
            if (far == i)
            {
                // printf("res %d\n", i);
                res.push_back(far - begin + 1);
                begin = i + 1;
            }
            // cout << far << ' ' << n << ' ' << i << endl;
        }

        return res;
    }
};

56. 合并区间

每次合并都更新下当前区间的左右两端点

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        sort(intervals.begin(), intervals.end(), [](vector<int>& vec1, vector<int>& vec2)
        {
            return vec1[0] < vec2[0];
        });

        int n = intervals.size();
        int start = intervals[0][0], end = intervals[0][1];
        for (int i = 1; i < n; i ++)
        {
            if (intervals[i][0] <= end)
            {
                start = min(start, intervals[i][0]);
                end = max(end, intervals[i][1]);
            }
            else
            {
                res.push_back({start, end});
                start = intervals[i][0], end = intervals[i][1];
            }
        }
        res.push_back({start, end});
        return res;
    }
};