题解 | #保卫家园#

保卫家园

https://ac.nowcoder.com/acm/problem/205068

参考文章: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维护这个集合;

全部评论

相关推荐

05-21 18:32
已编辑
湖南工学院 Java
这条干货多数是给i人朋友们分享的,知道你们开不了口,可以试试我说的这些方法1.调整心态:接受初期的尴尬刚开始进入一个新环境,双方都属于一个认识对方的过程,尴尬瞬间是难免存在的。首先,你要接受尴尬,允许自己犯错,实习期本身就是来学习的,同事也不会期待你完美无缺。另外,不要太以自我为中心,其实你的尴尬瞬间也许没有人在意,是因你的对自己的关注而放大了不安全感。2.准备一些防止尴尬的话题和工作相关的,可以以请教的方式开启。比如:xx,这个表格我没有看懂,可以给我讲一下吗非工作的话题,可以聊聊中午吃什么、当地的天气如何、通勤远不远之类的。比如:附近有什么好吃的外卖吗?我刚来还不太熟悉3.每日练习,逐渐打...
sweep^0416:内向人,遇到好的领导很重要,我之前一段实习组里全e人就我一个i 刚入职第一周还会带着我聊一下,后面越来越冷落我,实在受不了,每天去到就想亖,mentor还要pua说是我融入不了集体(我真的以为是我的问题)后面我离职了,去了现在这一家公司,我的领导也是e人,但是我融入的很好,组里的人全都很好很好,也不会出现小团体什么的,所以说内向不是不融入环境的根本,就是公司跟带教的问题
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务