算法基础课————区间贪心问题分类总结

作者： 作者的头像   Qiner ,  2025-03-25 22:13:39 · 湖北 ,  所有人可见 ,  阅读 8

1


1. 区间选点(最大不相交区间数量)

右端点排序

QQ20250325-213802.png

2. 区间分组(分成的组尽可能少)

左端点排序

QQ20250325-215324.png

维护每一个组的max_r，每次判断当前区间左端点是否大于min{max_r},是的话就放入当前组，否则将当前区间放入一个新组中

3. 区间覆盖

左端点排序

区间覆盖.png

1 评论

用户头像
Qiner   2025-05-04 16:31 · 湖北         踩      回复

区间分组的做法是正确的，我之前还以为有问题呢😭
今年天梯赛l2考了这个算法，但是也可以用扫描线做，但是我但是扫描线也没见过，这个贪心做法也以为不是完全对的，结果丢了好多分😭😭
还是我太菜了

1024
x