相互重叠的活动子集
Mutually Overlapping Subset of Activites
我正在准备期末考试，这是一道练习题。不是作业题。
我该如何着手攻击它？另外，更一般地说，我怎么知道什么时候使用贪婪编程和动态编程？直觉上，我认为这是使用贪心的好地方。我也在想，如果我能以某种方式创建一条正交线并 "sweep" 它，检查每个点的#of 交点并更新全局最大值，那么我就可以 return 最后的最大值的扫描。不过，我不确定如何通过算法进行平面扫描。
一个。给定一组活动 I1 ... In：每个 activity Ii 由其左点 Li 和右点 Ri 表示。设计一个非常有效的算法，找到最大数量的相互重叠的活动子集（用英语逐条写下你的解决方案）。
b。分析你的算法的时间复杂度。
建议的解决方案：
Ex 集合：{(0,2) (3,7) (4,6) (7,8) (1,5)}
区间 4-5 中最大值为 3
1) 将起点和终点拆分成两个单独的数组，并按非降序排列
起点：[0,1,3,4,7] (SP)
终点：[2,5,6,7,8] (EP)
我知道我可以使用两个指针来模拟平面扫描，但我不确定如何操作。我被困在这里了。
我想说你扫荡的想法很好。
平面扫掠不用担心，只用start/end点即可。将元素放入队列中。在每一步中，从队列前面取出较小的元素。如果它是起点，则增加当前任务计数，否则减少它。
由于您不需要指出哪些任务重叠 - 只需指出它们的数量 - 您无需担心特定任务的持续时间。
关于你的greedy vs DP问题，在我的非专业意见中，greedy不一定总能提供有效答案，而DP只适用于可以很好地分解成更小的子问题的问题。在这种情况下，我也不会调用您的扫描解决方案。
我正在准备期末考试，这是一道练习题。不是作业题。
我该如何着手攻击它？另外，更一般地说，我怎么知道什么时候使用贪婪编程和动态编程？直觉上，我认为这是使用贪心的好地方。我也在想，如果我能以某种方式创建一条正交线并 "sweep" 它，检查每个点的#of 交点并更新全局最大值，那么我就可以 return 最后的最大值的扫描。不过，我不确定如何通过算法进行平面扫描。
一个。给定一组活动 I1 ... In：每个 activity Ii 由其左点 Li 和右点 Ri 表示。设计一个非常有效的算法，找到最大数量的相互重叠的活动子集（用英语逐条写下你的解决方案）。
b。分析你的算法的时间复杂度。
建议的解决方案：
Ex 集合：{(0,2) (3,7) (4,6) (7,8) (1,5)} 区间 4-5 中最大值为 3
1) 将起点和终点拆分成两个单独的数组，并按非降序排列
起点：[0,1,3,4,7] (SP) 终点：[2,5,6,7,8] (EP)
我知道我可以使用两个指针来模拟平面扫描，但我不确定如何操作。我被困在这里了。
我想说你扫荡的想法很好。
平面扫掠不用担心，只用start/end点即可。将元素放入队列中。在每一步中，从队列前面取出较小的元素。如果它是起点，则增加当前任务计数，否则减少它。
由于您不需要指出哪些任务重叠 - 只需指出它们的数量 - 您无需担心特定任务的持续时间。
关于你的greedy vs DP问题，在我的非专业意见中，greedy不一定总能提供有效答案，而DP只适用于可以很好地分解成更小的子问题的问题。在这种情况下，我也不会调用您的扫描解决方案。