区间调度

10 分钟

给若干区间(活动),选最多个互不重叠的。贪心:按右端点从小到大排序,每次选右端点最早且不冲突的:sort(a,a+n,[](auto&x,auto&y){return x.r<y.r;}); 遍历时若 x.l>=lastR 就选它并更新 lastR

小纸条

区间 [1,3],[2,4],[3,5],最多选几个不重叠?

登录 后可看答案

区间调度 · 算法进阶 · op599 课程