Algorithm:贪心策略之区间覆盖问题

Describe
给定一个大区间1-T,以及n个小区间,要求用最少个数的小区间来覆盖大区间;

Input:
第一行,输入n和T;
随后n行输入对应区间的起始终止坐标
Output:
输出覆盖区间1-T所需的最少区间个数

Example

Input:
3 10
1 7
3 6
6 12
Output:
2

Thinking

首先应排除一些不可能用到的区间,比如右端点小于1和左端点大于T的区间;然后为满足贪心的思想,对于选择的第一个区间,必须使该区间的左端点<=1,右端点尽可能大;之后把此右端点当作基点,选择一个区间使它的左端点小于等于基点,右端点尽可能大,再把这个右端点当作基点,重复下去,如此才可能用最少小区间覆盖大区间;在这里插入图片描述
Notice:如果各区间的左端点都大于start,表示无解,因为start-左端点这一段始终无法被覆盖;

原文地址:https://www.cnblogs.com/Luweir/p/14147366.html