算法训练day38 LeetCode435.763.56.

435.无重叠区间

题目

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

题解

代码随想录 (programmercarl.com)

首先按左边界排列范围
再将长的重叠区间去除---并记录去除个数

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;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] >= end)
                end = intervals[i][1];
            else
            {
                end = min(end, intervals[i][1]);	//可以认为是去除了范围更大的区间
                count++;
            }
        }
        return count;
    }
};

763.划分字母区间

题目

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

题解

代码随想录 (programmercarl.com)

重叠区间的思路，统计字符出现的始末位置，排序，找到互不重叠的分组
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

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

56. 合并区间

题目

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

题解

代码随想录 (programmercarl.com)

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