AcWing 112. 雷达设备

题目链接：112. 雷达设备 - AcWing题库

对于 $x$ 轴上方的每个建筑物，可以计算出 $x$ 轴上的一段能管辖它的区间 $l[i] \sim r[i]$。

问题转化为：给定 $N$ 个区间，在 $x$ 轴上放置最少的点，使得每个区间至少包含一个点。

按照每个区间的左端点 $l[i]$ 从小到大排序，用一个变量维护已经安放的最后一台监控设备的坐标 $pos$，起初 $pos$ 为负无穷。

依次考虑每个区间。

如果当前区间 $i$ 的左端点 $l[i]$ 大于最后一台监控设备的坐标 $pos$，则新增一台设备，令 $pos = r[i]$。

否则就让最后一台已经安放的监控设备来管辖当前区间，并令 $pos = \min(r[i], pos)$。

以此类推，直至所有区间被管辖，输出安放的设备个数即可。

这个贪心算法可以用 “决策包容性” 来证明。

首先，对于每个区间 $l[i] \sim r[i]$，有两种选择：

1. 使用已有的监控设备管辖它；
2. 新建一台监控设备管辖它。

我们的贪心策略是，当选择 $1$ 可行时，不会选择 $2$。

选择 $1$ 之后，未来可以在任意位置新建一台监控设备。

而选择 $2$ 则需要在 $l[i] \sim r[i]$ 之间新建设备，也就是说，第 $1$ 项选择未来可能达到的状态包含了第 $2$ 项选择未来可能达到的状态。

其次，在选择 $1$ 之后，我们把上一台设备调整到 $\min(r[i], pos)$ 的位置，也就是在能管辖 $i$ 的前提下尽量往后放，“尽量往后放” 这个策略未来的可达状态显然也是包含了 “放在更靠前的位置” 未来的可达状态。

最后，因为所有区间已经按照 $l[i]$ 排序，所以这个调整不会影响到已经被管辖的区间，证必。

完整代码：雷达设备.cpp