代碼隨想錄刷題60Day

目錄

前言

無重疊區(qū)間（篩選區(qū)間）

劃分字母區(qū)間（切割區(qū)間）

?合并區(qū)間

前言

今日的重點是掌握重疊區(qū)問題。

無重疊區(qū)間（篩選區(qū)間）

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

劃分字母區(qū)間（切割區(qū)間）

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

?合并區(qū)間

文章來源地址http://www.zghlxwxcb.cn/news/detail-663284.html

   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;
                else
                    right = max(right, intervals[j][1]);
            }
            result.push_back({intervals[i][0], right});
            i = j - 1;
        }
        return result;
    }

到了這里，關(guān)于【算法日志】貪心算法刷題：重疊區(qū)問題(day31)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！