限制条件:
1<=n<=100000
1<=si<=ti,=109
样例:
输入
n=5
s={1,2,4,6,8}
T={3,5,7,9,10}
输出
3(选择工作1, 3, 5)
解题分析:
对这个问题,如果使用贪心算法的话,可能有以下几种考虑:
(1)、每次选取开始时间最早的;
(2)、每次选取结束时间最早的;
(3)、每次选取用时最短的;
(4)、在可选工作中,每次选取与最小可选工作有重叠的部分;
对于上面的四种算法,只有算法(2)是正确的,其它的三种都可以找到相应的反例。具体证明如下:
数轴上有n个区间,选出最多的区间,使得这些区间不互相重叠。
算法:
将所有区间按右端点坐标从小到大排序,顺序处理每个区间。如果它与当前已选的所有区间都没有重叠,则选择该区间,否则不选。
证明:
显然,该算法最后选出的区间不互相重叠,下面证明所选出区间的数量是最多的。设fi为该算法所接受的第i个区间的右端点坐标,gi为某最优解中的第i个区间的右端点坐标。
命题1.1 当i>=1时,该算法所接受的第i个区间的右端点坐标fi<=某最优解中的第i个区间的右端点坐标gi。
该命题可以运用数学归纳法来证明。对于i=1,命题显然为真,因为算法第一个选择的区间拥有最小右端点坐标。令i>1,假定论断对i-1为真,即fi-1<=gi-1。则最优解的第i个可选区间所组成的集合包含于执行该算法时第i个可选区间所组成的集合;而当算法选择第i个区间时,选的是在可选区间中右端点坐标最小的一个,所以有fi<=gi。证毕。
设该算法选出了k个区间,而最优解选出了m个区间。
命题1.2 最优解选出的区间数量m=该算法选出的区间数量k。
假设m>k,根据命题1.1,有fk<=gk。由于m>k,必然存在某区间,在gk之后开始,故也在fk之后开始。而该算法一定不会在选了第k个区间后停止,还会选择更多的区间,产生矛盾。所以m<=k,又因为m是最优解选出区间个数,所以m=k。
综上所述,算法选出的区间是最优解。
#include <stdio.h>
#include <tchar.h>
#include <queue>
#include "iostream"
using namespace std;
const int N = 5;
int s[N]={1,2,4,6,8};
int t[N]={3,5,7,9,10};
int solve()
{
pair<int, int> itv[N];
for(int i = 0; i < N; i ++) {
itv[i].first = s[i];
itv[i].second = t[i];
}
sort(itv, itv + N);
int count = 0;
int t = 0;
for(int i = 0; i < N; i ++) {
if(t < itv[i].first) {
count ++;
t = itv[i].second;
}
}
return count;
}
int main() {
cout << solve() << endl;
return 0;
}