題目：選N個(gè)課程，每個(gè)課程開始和結(jié)束時(shí)間分別是a, b
問：分身成幾個(gè)人，可以完美上所有課程？

區(qū)間貪心版

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

struct node
{
    int m_begin_time;
    int m_end_time;
    int m_flag = false;
};

int Compare(const node &a, const node &b){
    return a.m_begin_time == b.m_begin_time ? a.m_end_time < b.m_end_time : a.m_begin_time < b.m_begin_time;
}

int CountBlock(vector<node> &courses, int depth){
    if(courses.size() == 0){
        return depth;
    }else if(courses.size() == 1){
        return depth + 1;
    }
    vector<int> cluster;
    int start = courses[0].m_begin_time;
    int end = courses[0].m_end_time;
    cluster.push_back(0);
    for(int i=1; i<courses.size(); i++){
        if(courses[i].m_begin_time >= end){
            cluster.push_back(i);
            start = courses[i].m_begin_time;
            end = courses[i].m_end_time;
        }
    }
    for(int i=cluster.size()-1; i>=0; i--){
        courses.erase(courses.begin() + cluster[i]);
    }
    return CountBlock(courses, depth+1);
}

int main()
{
    int N;
    cin >> N;
    vector<node> courses(N);
    for(int i=0; i<N; i++){
        cin >> courses[i].m_begin_time;
        cin >> courses[i].m_end_time;
    }
    sort(courses.begin(), courses.end(), Compare);
    cout << CountBlock(courses, 0);
    return 0;
}

染色版

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

/*
 * 題目：選N個(gè)課程，每個(gè)課程開始和結(jié)束時(shí)間分別是a, b
 * 問：分身成幾個(gè)人，可以完美上所有課程？
 * 采用染色的方法
*/


int main()
{
    int N;
    cin >> N;
    vector<int> my_time(1000000, 0);
    int begin, end;
    int max_end = 0;
    for(int i=0; i<N; i++){
        cin >> begin >> end;
        max_end = max(max_end, end);
        for(int j=begin; j<end; j++){
            my_time[j]++;
        }
    }
    int max_count = 0;
    for(int i=0; i<=end; i++){
        max_count = max(max_count, my_time[i]);
    }
    cout << max_count;
    return 0;
}

染色離散化版

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

/*
 * 題目：選N個(gè)課程，每個(gè)課程開始和結(jié)束時(shí)間分別是a, b
 * 問：分身成幾個(gè)人，可以完美上所有課程？
 * 思路：
 * 1.將所有課程左端點(diǎn)排序。
 * 2.根據(jù)貪心，查找出不沖突的區(qū)間號，區(qū)間個(gè)數(shù)。
 * 3.去掉這些不沖突的區(qū)間號?；氐?（因?yàn)椴恍枰俅闻判颍? *
 * 只通過了%50.
 * 優(yōu)化點(diǎn)1：vector數(shù)組的erase非常消耗大，優(yōu)化上可以考慮用標(biāo)記來解決。（優(yōu)化后沒解決）
 * 優(yōu)化點(diǎn)2：采用list容器，可以降低刪除的成本。（重新寫代碼有點(diǎn)困難，因?yàn)椴僮鞣绞讲煌? * 
*/


struct node
{
    int m_begin_time;
    int m_end_time;
    int m_flag = false;
};

int Compare(const node &a, const node &b){
    return a.m_begin_time == b.m_begin_time ? a.m_end_time < b.m_end_time : a.m_begin_time < b.m_begin_time;
}

int main()
{
    int N;
    cin >> N;
    vector<node> courses(N);
    vector<int> all_count;
    for(int i=0; i<N; i++){
        cin >> courses[i].m_begin_time;
        cin >> courses[i].m_end_time;
        courses[i].m_end_time--;
        all_count.push_back(courses[i].m_begin_time);
        all_count.push_back(courses[i].m_end_time);
    }
    sort(all_count.begin(), all_count.end());
    int key = unique(all_count.begin(), all_count.end())-all_count.begin();//內(nèi)部實(shí)現(xiàn)
    int color[key+7];
    memset(color, 0, sizeof(color));
    for (int i=0; i<N; i++) {
        int L = lower_bound(all_count.begin(), all_count.begin()+key, courses[i].m_begin_time) - all_count.begin();
        int R = lower_bound(all_count.begin(), all_count.begin()+key, courses[i].m_end_time) - all_count.begin();
        color[L]++;
        color[R+1]--;
    }
    for (int i = 1; i<key; i++) {
        color[i] = color[i-1]+color[i];
    }
    int ans = 0;
    for (int i = 0; i<key; i++){
        ans = max(ans, color[i]);
    }
    cout << ans;
}

優(yōu)先隊(duì)列時(shí)間線版

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


struct node
{
    int m_begin_time;
    int m_end_time;
    int m_flag = false;
};

int Compare(const node &a, const node &b){
    return a.m_begin_time == b.m_begin_time ? a.m_end_time < b.m_end_time : a.m_begin_time < b.m_begin_time;
}

int main()
{
    int N;
    cin >> N;
    vector<node> courses(N);
    vector<int> all_count;
    for(int i=0; i<N; i++){
        cin >> courses[i].m_begin_time;
        cin >> courses[i].m_end_time;
    }
    sort(courses.begin(), courses.end(), Compare);
    priority_queue<int, vector<int>, greater<int> > pri_queue;
    for(int i=0; i<N; i++){
        if(pri_queue.empty()){
            pri_queue.push(courses[i].m_end_time);
        }else{
            auto smallest = pri_queue.top();
            if(smallest <= courses[i].m_begin_time){// 無需開一條時(shí)間線
                int temp = courses[i].m_end_time;
                pri_queue.pop();
                pri_queue.push(temp);
            }
            else{//開一條新的時(shí)間線
                pri_queue.push(courses[i].m_end_time);
            }
        }
    }
    cout << pri_queue.size();
}