<分区>
我无法解决这个问题:假设我们有 M 灯。起初他们都关闭了。一个人做N个 Action 。移动是指此人将所有灯从 a 切换到 b(含)。问题是:这些 Action 之后会有多少灯泡亮起。限制是:
这是一个示例输入:
12 3
2 6
2 6
1 3
这意味着有 12 个灯泡，这个人做了 3 个 Action 。在他的第一步中，他将灯 2 切换到 6(所以现在我们打开了 2、3、4、5 和 6)。在他的第二个 Action 中，他再次将灯 2 切换到 6(所以现在所有灯都再次关闭)。在他的最后一步中，他将灯 1 切换到灯 3(灯 1,2 和 3 亮起)。所以答案是 3，因为在这一系列 Action 之后只有 3 盏灯亮着。
我需要一些帮助来解决我应该如何解决这个问题。简单地创建一个 bool 数组并切换它是行不通的，因为数字会变得很大。
最佳答案
假设您不需要动态数据结构(其中您有连续的更新/查询)，我会使用扫描技术来解决这个问题，使用一个简单的逻辑:
1) 对所有段结束进行排序(在您的示例中，结果为 [1, 2, 2, 3, 6, 6])
2) 扫描列表，维护一个“奇偶校验”变量。每当您遇到新的结束时，请切换奇偶校验。扫描仅访问末端，因此扫描的任何步骤都“看到”灯泡处于相同状态(打开或关闭，取决于奇偶校验变量)的段。
伪代码:
countTurnedOn(L : Array of Segment objects) {
E = create empty list
for (all s in L) {
E.add(s.begin)
E.add(s.end+1)
}
sort(E)
count = 0
parity = 0
pos = 0
for (i in 0 .. E.length-1) {
newpos = E[i]
count = count + (newpos - pos) * parity
parity = (parity + 1) % 2
pos = newpos
}
return count
}
关于algorithm - 寻找算法(低内存占用): Toggling lights，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20727555/