覆盖区间有关问题
覆盖区间问题
覆盖区间问题
给一个大区间，再给出N个小区间，求出最少用多少个区间可以把大区间覆盖完.
本人算法是这样：
1，首先以大区间作为目标区间，列出每个小区间对目标区间覆盖的长度，从中选出最大值，存入lmax;
2，if
lmax只有一个值，则将该区间并入结果；
else
设这么多个具有lmax值的区间为xi,(i=1,2,3...n),分别以xi作为目标区间，列出其余区间对目标区间覆盖的长度，求出最小值。将最小值对应的xi作为并入结果 的区间并入结果。
3，更新目标区间为减去上一步中并入结果的区间，然后更新列出每个余下的小区间对目标区间覆盖的长度，重复123步，直到目标区间为空。
O（N*N）。用贪心算法解，还有什么方法。
------解决方案--------------------
算法是错的!
假设要覆盖的区间是[0,10],而给出的小区间是下面几个:
[0,5]
[5,10]
[0,1]
[1,9]
[9,10],
很明显,[0,5]和[5,10]两个区间就可以完成对大区间的完全覆盖。
可是按照你的算法，先取出来的是[1,9]，这样无论如何都得再选两个区间才能完成全覆盖。不应该用贪心算法，感觉应该是动态规划。
------解决方案--------------------
假设大区间为（a,b）;
首先在所有的小区间,计算跟大区间的重叠区域(a,a'],选择最大的a'所在的区间；
递归判断区间（a',b），最少用多少个区间可以把大区间覆盖完；
------解决方案--------------------
无解吧。
需要多少半径为1的员圆可以覆盖半径为2的圆
覆盖区间问题
给一个大区间，再给出N个小区间，求出最少用多少个区间可以把大区间覆盖完.
本人算法是这样：
1，首先以大区间作为目标区间，列出每个小区间对目标区间覆盖的长度，从中选出最大值，存入lmax;
2，if
lmax只有一个值，则将该区间并入结果；
else
设这么多个具有lmax值的区间为xi,(i=1,2,3...n),分别以xi作为目标区间，列出其余区间对目标区间覆盖的长度，求出最小值。将最小值对应的xi作为并入结果 的区间并入结果。
3，更新目标区间为减去上一步中并入结果的区间，然后更新列出每个余下的小区间对目标区间覆盖的长度，重复123步，直到目标区间为空。
O（N*N）。用贪心算法解，还有什么方法。
------解决方案--------------------
算法是错的!
假设要覆盖的区间是[0,10],而给出的小区间是下面几个:
[0,5]
[5,10]
[0,1]
[1,9]
[9,10],
很明显,[0,5]和[5,10]两个区间就可以完成对大区间的完全覆盖。
可是按照你的算法，先取出来的是[1,9]，这样无论如何都得再选两个区间才能完成全覆盖。不应该用贪心算法，感觉应该是动态规划。
------解决方案--------------------
假设大区间为（a,b）;
首先在所有的小区间,计算跟大区间的重叠区域(a,a'],选择最大的a'所在的区间；
递归判断区间（a',b），最少用多少个区间可以把大区间覆盖完；
------解决方案--------------------
无解吧。
需要多少半径为1的员圆可以覆盖半径为2的圆