#205. Cleaning Shifts
Cleaning Shifts
题目描述
选择若干个闭区间,使它们覆盖给定整数时间段内的每个整数时刻,求最小费用。如果无法覆盖,输出 −1。
书目本条同时列出 POJ2376 和 POJ3171。本包在同一题中保留两种输入格式,按首行整数的个数区分。
输入格式
无权版本 POJ2376: 首行 n、T,随后 n 行每行 l、r;需要覆盖 [1,T],每个区间费用为 1。
带权版本 POJ3171: 首行 n、L、R,随后 n 行每行 l、r、w;需要覆盖 [L,R],选择该区间的费用为 w。
1≤n≤25000,1≤T≤1000000;带权版本 1≤L≤R≤86399,1≤w≤500000。区间端点均为整数且 l≤r。区间包含其两个端点。两种版本均仅有一组数据。
输出格式
最小总费用,或 −1。
示例
3 10
1 7
3 6
6 10
2
配套说明
原包两份“数据压缩包”实际为旧下载网页。本题数据补生成,两个版本的答案分别使用配套的对应参考程序计算。提交程序应兼容上述两种首行格式。