区间选点(最大不相交区间数量)
区间分组(分成的组尽可能少)
维护每一个组的max_r,每次判断当前区间左端点是否大于min{max_r},是的话就放入当前组,否则将当前区间放入一个新组中
max_r
min{max_r}
区间覆盖
区间分组的做法是正确的,我之前还以为有问题呢😭 今年天梯赛l2考了这个算法,但是也可以用扫描线做,但是我但是扫描线也没见过,这个贪心做法也以为不是完全对的,结果丢了好多分😭😭 还是我太菜了
区间分组
区间分组
的做法是正确的,我之前还以为有问题呢😭今年天梯赛l2考了这个算法,但是也可以用扫描线做,但是我但是扫描线也没见过,这个贪心做法也以为不是完全对的,结果丢了好多分😭😭
还是我太菜了