且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

区间调度问题

更新时间:2022-08-18 13:47:24

区间调度问题
区间调度问题

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 100000;

int N,S[MAX_N],T[MAX_N];

pair<int,int> itv[MAX_N];

void solve()
{
    for(int i=0;i<N;i++)
    {
        itv[i].first=T[i];
        itv[i].second=S[i];
    }
    sort(itv,itv+N);

    int ans=0,t=0;
    for(int i=0;i<N;i++)
    {
        if(t<itv[i].second)
        {
            ans++;
            t=itv[i].first;
        }
    }

    printf("%d\n",ans);
}

int main()
{
    printf("N:\n");
    scanf("%d",&N);

    printf("S[%d]",N);
    for(int i=0;i<N;i++)
    {
        scanf("%d",&S[i]);
    }

    printf("T[%d]",N);
    for(int i=0;i<N;i++)
    {
        scanf("%d",&T[i]);
    }

    solve();

    return 0;
}