区间问题

区间调度问题

有n项工作，每项工作分别在si时间开始，在ti时间结束。对于每项工作，你都可以选择参与与否。如果选择了参与，那么自始至终都必须全程参与。此外，参与工作的时间段不能重叠（即使是开始的瞬间和结束的瞬间的重叠也是不允许的）。

你的目的是参与尽可能多的工作，那么最多能参与多少项工作呢？

限制条件

1<=N<=100000

1<=si<=ti<=10^9

样例

输入

n=5,s={1,2,4,6,8},t={3,5,7,9,10}

输出

3

题解

有题可知我们应该在可选的工作中，每次都选取结束时间最早的工作。

代码

#include<stdio.h> #include<stdlib.h>    //qsort函数函数头

int n;

typedef struct{       //结构体数组，存放工作开始时间和结束时间     int frist;     //开始时间     int second;    //结束时间 }s;

s pair[100010];

int cmp(const void *a ,const void * b)    //定义排序方式 {     return (((s *)a)->frist>((s *)b)->frist?1:-1); }

int main() {     int i,ans=0,t;     scanf("%d",&n);     for(i=0;i<n;i++)     {         scanf("%d",&pair[i].frist);     }     for(i=0;i<n;i++)     {         scanf("%d",&pair[i].second);     }

    qsort(pair,n,sizeof(pair[0]),cmp);  //快速排序 时间复杂度nlogn

    for(i=0;i<n;i++)     {         if(t<pair[i].frist)    //t为最后选择工作的结束时间         {             ans++;             t=pair[i].second;         }     }

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