algorithm - 确定灯泡是否可以在给定范围内打开

Question

假设您有 N 个排成一排的灯泡。您还有 M 开关，其形式为 L 到 R，可用于切换范围内的灯泡状态 L 到 R，包括两者。

我如何确定是否存在通过使用这些 M 开关中的任何一个来打开所有灯泡的方法，任意次数？ (我只想知道可不可以)

一种直接的方法是尝试所有可能的开关组合，并检查灯泡是否全部打开。但这是非常低效的。有没有更好的方法来做同样的事情？

灯泡和开关的数量限制为 1000。

示例:

如果有 10 个灯泡和 3 个在 1 到 7 范围内切换灯泡的开关, 6 到 7, 6 到 10, 然后我们可以使用所有的开关一次, 并打开从 1 到 10 的所有灯泡都亮了。

Answer 1

梅林是对的。如果您使用部分主元来实现 LU 分解，那么通过仔细的主元选择，您可以确保减少的行始终是间隔的。真正引人注目的部分是，在进一步分析时，我们甚至不需要进行分解。它实际上足以确定图中 1 和 N+1 之间是否存在路径，其中每个开关 L..R 产生一条边{L, R+1}。