Algorithm:贪心策略之区间选点问题

Describe:在数轴上标点,使得该点能够被区间覆盖,并要求对应区间最少覆盖Ki个点,求最少标多少个点保证满足要求,同一个位置不能重复;

Input:
第一行输入区间个数 n
后面n行输入对应区间的起始坐标,终点坐标以及需覆盖点的个数
Output:
最少所需点的个数

Example

Input:
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Output:
6

Thinking
首先依旧对所有区间按终点坐标进行排序,然后在终点坐标处进行打点,因为在这个位置打点能够被尽可能多的区间所覆盖;如果该区间覆盖的点的数目达不到要求,就从终点坐标开始向左依次打点,如果此处已打点,则跳过;
在这里插入图片描述
代码等回家再上吧,有许多要注意的地方;

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