题目重点：将闭区间改为半开边界，前缀质量积分查询窗口，枚举所有斜率变化点。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 坐标为整数，闭区间[l,r]含r-l+1个袋，value非负，区间间隙价值0。
- 窗口可放任何整数起点，长度k>0；区间不能重叠，空输入返回0。
解题路线
- 不能展开所有坐标，巨大间隙可能使空间爆炸。将每段变[l,r+1)，前缀数组存完整段质量(length·value)。
- 定义F(x)=坐标严格小于x的价值总和。二分定位最后start≤x的段，完整此前质量加当前段截断长度；x落间隙时截到段end即可。窗口[s,s+k)价值F(s+k)-F(s)。
- F是连续分段线性，斜率仅在每段start与end改变。窗口价值斜率改变只可能在这些edge或edge-k，因此最大值在某个候选边界达到；平坦最大区间同样可以取端点。
- 枚举所有edge和edge-k，用两个F查询评价，O(n)候选无需扫坐标宽度。这里枚举全部边界更容易完整证明，之后可讨论双指针压到线性处理。
- 注意闭区间右端需要+1。若误用r，单个袋[l,l]长度会变0且窗口边界全部错一位。
手动走一遍
训练segments=[(1,3,2),(10,10,9)]、k=3，窗口[8,10]价值9，超过[1,3]的6；不必跨巨大间隙逐坐标枚举。若k足够大可同时包含两段，总15。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from bisect import bisect_right
def maximum_k_bags(segments,k):
"""Disjoint inclusive integer intervals; nonnegative per-position values."""
if k <= 0 or any(l>r or v<0 for l,r,v in segments):
raise ValueError("invalid window or intervals")
ordered=sorted(segments)
if any(ordered[i-1][1] >= ordered[i][0] for i in range(1,len(ordered))):
raise ValueError("overlapping segments")
starts=[l for l,r,v in ordered]
prefix=[0]
endpoints=[]
for l,r,v in ordered:
prefix.append(prefix[-1]+(r-l+1)*v)
endpoints.extend((l,r+1))
def mass_before(x):
i=bisect_right(starts,x)-1
if i < 0: return 0
l,r,v=ordered[i]
return prefix[i]+(min(x,r+1)-l)*v
return max((mass_before(s+k)-mass_before(s)
for edge in endpoints for s in (edge,edge-k)),default=0)
复杂度
排序O(n log n)，4n候选各O(log n)查询，总O(n log n)时间与O(n)空间；与坐标上界无关，数值乘法须检查宽度。
易错点与追问
容易失分的边界
- 展开10^12坐标。
- r-l代替r-l+1。
- 只试段起点，漏掉以段尾对齐的窗口。
- 重叠段仍用单段F公式。
继续深挖
- 区间重叠如何先聚合成不重叠常值段？
- 负value且窗口必须落指定范围怎样改？
- 双指针如何利用单调候选减少二分？
