## 问题描述 有n项工作，每项工作分别在Si时间开始，在ti时间结束。对于每项工作，你都可以选择参与与否。如果选择了参与，那么自始至终都必须全程参与。此外，参与工作的时间段不能重叠（即使是开始的瞬间和结束的瞬间的重叠也是不允许的） 你的目标是参与尽可能多的工作，那么最多能参与多少项工作呢？ **数据范围：** 1 ≤ n ≤ 1e5 1 ≤ si ≤ ti ≤ 1e9 **样例：** 输入 n=5 S={1,2,4,6,8} t={3,5,7,9,10} 输出 3(选择工作1, 3, 5) ## 问题分析 我们就是想提高教室地利用率，尽可能多地安排活动。 考虑容易想到的几种贪心策略： 1. 每次选取开始时间最早的； 2. 每次选取用时最短的； 3. 在可选工作中，每次选取与最小可选工作有重叠的部分； 4. 每次选取结束时间最早的； 我们可以利用反证法来证明前三个命题是错误的： 1. 开始最早的活动优先，目标是想尽早结束活动，让出教室。 然而， 这个显然不行，因为最早的活动可能很长，影响我们进行后面的活动。例如活动开始和结束时间分别为\[0, 100), \[1,2) ,\[2, 3), \[3, 4),\[4,5\]，安排［0，100)的这个活动之后，其他活动无法安排，可是最优解是安排除它外的4个活动。 2. 短活动优先， 目标也是尽量空出教室。 但是不难构造如下反例： \[0,5) \[5,10) \[3, 7), 这里\[3,7)最短，但如果我们安排了\[3,7)，其它两个无法安排了。但是最优解显然是安排其它两个，而放弃\[3,7)，可见这个贪心策略也是不行的。 3. 最少冲突的活动优先， 既然上面安排活动是想减少冲突，那么如果我们优先安排冲突最少的活动可以么？至少从（1）和（2）看来，这个策略是有效的。真是对的么？ 尝试这个例子： \[0,2) \[2,4) \[4,6) \[6,8) \[1,3) \[1,3) \[1,3) \[3,5) \[5,7) \[5,7) \[5,7)  \[0,2) 和3个活动冲突——3个\[1,3) \[2,4)和4个活动冲突3个\[1,3)和一个\[3,5) \[4,6)和也和4个活动冲突3个\[5,7)和一个\[3,5) \[6,8)和3个活动冲突——3个\[5,7) 下面\[1,3)和\[5,7)每个都和5个活动冲突， 而\[3,5)只和两个活动冲突——\[2,4)和\[4,6)。 那按照我们的策略应该先安排\[3,5), 可是一旦选择了\[3,5)，我们最多只可能安排3个活动。 但明显第一行的4个活动都可以安排下来，所以这种策略也是不对的。 4. 结束时间越早的活动优先。这个策略是有效的，我们可以证明。假设最优解OPT中安排了m个活动，我们把这些活动也按照结束时间由小到大排序，显然是不冲突的。假设排好顺序后，这些活动是a(1) , a(2), a(3)….am 假设按照我们的贪心策略，选出的活动自然是按照结束时间排好顺序的，并且也都是不冲突的，这些活动是b(1), b(2) …b(n) 问题关键是，假设a(1) = b(1), a(2) = b(2)…. a(k) = b(k)，但是a(k+1) != b(k+1)，回答几个问题： (1) b(k+1)会在a(k+2), a(k+3), …. a(m)中出现么？ 不会。因为b(k+1)的结束时间是最早的，即f(b(k+1)) <= f(a(k+1)),而a(k+2), a(k+3), …. a(m)的开始时间和结束时间都在f(a(k+1))之后，所以b(k+1)不在其中。 (2) b(k+1)和a(1), a(2), …. a(k) 冲突么？ 不冲突，因为a(1), a(2), …. a(k)就是b(1), b(2), …. b(k) (3) b(k+1)和a(k+2), a(k+3), …. a(m)冲突么？ 不冲突，因为f(b(k+1)) <= f(a(k+1))，而a(k+2), a(k+3), …. a(m)的开始时间都在f(a(k+1))之后，更在f(b(k+1))之后。 因此我们可以把a(k+1) 换成b(k+1)， 从而最优解和我们贪心得到的解多了一个相同的，经过一个一个替换，我们可以把最优解完全替换成我们贪心策略得到的解。 从而证明了这个贪心策略的最优性。 （以上讲解来自51Nod） ## Code ~~~ #include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define ms(a,b) memset(a,b,sizeof(a)) #define INF 0x7f7f7f7f const int maxn=1e6+10; const int mod=1e9+7; using namespace std; struct node { int start,end; }p[11000]; int cmp(node u,node v) { //结束时间相同，选择开始时间晚的 if(u.end==v.end) return u.start>v.start; //结束时间不同，选择结束早的 else   return u.end<v.end; } int main(int argc, char const *argv[]) { ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>p[i].start>>p[i].end; sort(p,p+n,cmp); int sum=1; for(int i=1,k=p[0].end;i<n;i++) { if(p[i].start>=k) { sum++; k=p[i].end; } } cout<<sum<<endl; return 0; } ~~~ 对应题目：[HDU2037](http://acm.hdu.edu.cn/showproblem.php?pid=2037)