[TOC]
## 区间调度
### 题目描述
有n项工作, 每项工作的起止时间为[s[i], t[i]]. 对于每项工作, 你都可以选择是否参加, 但是如果参加一项工作后, 就必须在该项工作的起止时间内全程参与, 同一时刻你只能参加一种工作. 问最多可以参加多少项工作. (可以在结束的时刻开始新的工作)
* * * * *
### 输入
第一行, 一个正整数n(1<=n<=2000), 表示有多少项工作. 以下n行, 每行两个整数s[i],ti, 表示第1~n项工作的开始和结束时刻.
* * * * *
### 输出
输出最多能参加的工作数.
* * * * *
### 代码实现
```
#include<iostream>
#include<algorithm>
using namespace std;
struct Node{
int start;
int end;
}nodes[2005];
bool cmp(Node node1,Node node2){
return node1.end < node2.end;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i ++){
cin >> nodes[i].start >> nodes[i].end ;
}
sort(nodes,nodes+n,cmp);
int cnt = 0;
int pos = 0;
for(int i = 0; i < n; i ++){
if( pos <= nodes[i].start ){
cnt += 1;
pos = nodes[i].end;
}
}
cout << cnt << endl;
}
```
### 分析
区间调度是贪心算法的一种典型例题，对于区间调度，普遍的解法是将结构体或数组按照结束时间排序，我们的策略是优先选取结束时间早的时间，这样可以尽可能选择多的事件。
* * * * *
核心代码如下
```
int pos = 0;
int cnt = 0;
for(int i = 0; i < n; i ++){
if( pos <= nodes[i].start ){
cnt += 1;
pos = nodes[i].end;
}
}
```
用pos来存储结束时间，cnt用来表示可以参加多少件事件，如果当前结束时间小于或者等于下一个事件的开始时间，我们就将cnt加一
