#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

配套说明

原包两份“数据压缩包”实际为旧下载网页。本题数据补生成,两个版本的答案分别使用配套的对应参考程序计算。提交程序应兼容上述两种首行格式。