约 10 分钟
给若干区间(活动),选最多个互不重叠的。贪心:按右端点从小到大排序,每次选右端点最早且不冲突的:sort(a,a+n,[](auto&x,auto&y){return x.r<y.r;}); 遍历时若 x.l>=lastR 就选它并更新 lastR。
sort(a,a+n,[](auto&x,auto&y){return x.r<y.r;});
x.l>=lastR
lastR
区间 [1,3],[2,4],[3,5],最多选几个不重叠?
登录 后可看答案