algorithm - 相互重叠的事件子集

Question

我正在准备期末考试，这是一道练习题。这不是作业问题。

我该如何着手攻击它？另外，更一般地说，我怎么知道什么时候使用贪婪编程和动态编程？直觉上，我认为这是使用贪心的好地方。我也在想，如果我能以某种方式创建一条正交线并“扫描”它，检查每个点的#of 交点并更新全局最大值，那么我就可以在扫描结束时返回最大值。不过，我不确定如何通过算法进行平面扫描。

一个。给定一组事件 I1 ... In:每个事件 Ii 由其左点 Li 和右点 Ri 表示。设计一个非常有效的算法，找到最大数量的相互重叠的事件子集(用英语逐条写下你的解决方案)。

分析算法的时间复杂度。

建议的解决方案:

Ex 集合:{(0,2) (3,7) (4,6) (7,8) (1,5)}最大值为 3 从区间 4-5

1) 将起点和终点拆分成两个单独的数组，并按非降序排列

起点:[0,1,3,4,7] (SP)终点:[2,5,6,7,8] (EP)

我知道我可以使用两个指针来模拟平面扫描，但我不确定如何操作。我被困在这里。

Answer 1

我想说你的扫荡想法很好。

您无需担心平面扫描，只需使用起点/终点即可。将元素放入队列中。在每一步中，从队列前面取出较小的元素。如果它是起点，则增加当前任务计数，否则减少它。

由于您不需要指出哪些任务是重叠的 - 只需指出它们的数量 - 您无需担心特定任务的持续时间。

关于你的贪婪与 DP 问题，在我的非专业意见中，贪婪可能并不总是提供有效答案，而 DP 仅适用于可以很好地划分为更小子问题的问题。在这种情况下，我也不会调用您的清除解决方案。