问题描述：有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
分析：一般会有下列几种想法：
（1）在可选的工作中，每次都选取开始时间最早的工作。
（2）在可选的工作中，每次都选取结束时间最早的工作。
（3）在可选的工作中，每次都选取用时最短的工作。
（4）在可选的工作中，每次都选取与最少可选工作有重叠的工作。
算法（2）是正确的，其余的在某些情况下，它们所取的工作并非最优。如对（3）：输入n=3,s={1,3,5},t={4,6,9},最优解应为2（选1-4 5-9这两段），但（3）的答案为1，会选3-6。
算法（2）代码如下：
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 const int MAX_N=100000; 6 7 int N,S[MAX_N],T[MAX_N]; 8 pair<int,int> itv[MAX_N];//工作区间 9 10 int main() 11 { 12 cin>>N; 13 for(int i=0; i<N; i++){ 14 cin>>S[i]; 15 } 16 for(int i=0; i<N; i++){ 17 cin>>T[i]; 18 } 19 20 for(int i=0; i<N; i++){ 21 itv[i].first=T[i];//为了让结束时间早的工作排在前面，把T存入first 22 itv[i].second=S[i];//，S存入second(总之是为了下面排序的方便) 23 } 24 sort(itv,itv+N); 25 26 int ans=0,t=0; 27 for(int i=0; i<N; i++){ 28 if(t<itv[i].second){//上一件工作结束时间<上一件工作开始时间 29 ans++; 30 t=itv[i].first; 31 } 32 } 33 cout<<ans; 34 return 0; 35 }
原文：https://www.cnblogs.com/Si-wuxie/p/12201764.html