题解 | #活动安排#

说是贪心，我更愿称其为动态规划吧

#include <algorithm>
#include<iostream>
#include <utility>
#include <vector>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}

int GreedForCounter(vector<pair<int, int>>& Act){
    int result = 1, temp = Act[0].second;
    for(int j = 1; j < Act.size(); j++){
        // 只要后面的开始时间段比现在的结束时间大，就可计算，且因为排序了，所以优先选择了最小结束时间的段
        if(temp <= Act[j].first){
            result++;
            // 动态更新
            temp = Act[j].second;
        }
    }
    return result;
}

int main(){
    int OpTimes = 0;
    vector<pair<int, int>> Activity;
    cin >> OpTimes;
    for(int i = 0; i < OpTimes; i++){
        pair<int, int> temp = {0,0};
        cin >> temp.first >> temp.second;
        Activity.push_back(temp);
    }
    // 排序，以简化后面的活动数量计算
    sort(&Activity[0], &Activity[OpTimes], compare);
    int counter = GreedForCounter(Activity);
    cout << counter;
    return 0;
}