$区间最优覆盖问题$区间最优覆盖问题

Description

给出一个长度为 $Len$Len 的区间 $A$A, 再给出 $N$N 个不同的区间
求 $A$A 一次性最多覆盖多少区间, 并且输出该方案的 $A$A左端点下标

Solution

首先舍弃那些长度比 $Len$Len大的区间, 设每个区间左端点 $L$L, 右端点 $R$R,
然后使用每个区间对差分数组进行更新:

• 在 $R-Len+1$R−Len+1位置加 $1$1
• 在 $R+1$R+1位置减 $1$1

最后使用该区间从左往右扫一遍, 中间取最大值即可

例题