参考文章:https://blog.csdn.net/qq_41286356/article/details/106892022
问题等价:从集合中选取若干个区间集合,每个区间中相互覆盖重叠的区间个数不超过k个,问最多能选取多少个区间;
贪心思路:
1、枚举区间的起点,每次维护一个大小为k的集合,集合内只存放区间【l,r】范围内的r;
(枚举起点的必要性:如果不枚举起点,eg:n = 4,k = 2;【1,2】,【1,3】,【2,7】,【2,9】, 当前三个加入set后,set运行到第四个时set中内容为2,3,7;此时set中最后一个元素为7,但是我们实际要删除的是【1,3】,因为这个在前面, 所以一定要枚举起点,每次将set中元素小于当前起点的值删除)
2、如果集合大小小于k,直接将元素放入集合;
3、如果集合大于k,将集合中r最大的那个弹出集合,表示这个人没有入伍(即覆盖不了)ans++;
4、ans就是最终答案,由于会有重复,所以用multiset维护这个集合;