贪心算法区间调度问题

greedy-schedule.cc

/* 贪心算法
 * 区间调度问题
 *
 * 有n项工作, 每项工作分别在si时间开始, 在ti时间结束.
 * 对于每项工作都可以选择是否参与, 一旦参与就必须全程参与.
 * 参与工作的时间段不能重叠
 * 问最多参与多少项工作
 *
 * 算法:
 * 每次选择结束时间最早的工作
 *
 */

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

using namespace std;

int main(){
    int n, tmp;
    vector<int> s;
    vector<int> t;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> tmp;
        s.push_back(tmp);
    }
    for(int i=0; i<n; i++){
        cin >> tmp;
        t.push_back(tmp);
    }

    vector<pair<int, int> > itv;
    for(int i=0; i<n; i++){
        itv.push_back(make_pair<int, int>(t[i], s[i]));
    }
    sort(itv.begin(), itv.end());
    int ans = 0, time = 0;
    for(int i=0; i<n; i++){
        if(time < itv[i].second){
            ans ++;
            time = itv[i].first;
        }
    }

    cout << ans << endl;
}