j*****n
发帖数: 1545 | 1 有 n 个 线段， 每个线段表示为 [ x_start_n, x_end_n ]. 然后我想把所有这些线
段都map到 x axis 上， 但不能互相有 overlap. 问题就是最少开几个 x 轴能把这些
线段都map上来， 但互相不能有overlap。
比如:
线段1:［1, 3]
线段2: [ 2, 4]
线段3: [ 3, 5]
线段4: [4, 6]
我最少可以map到2个 x 轴上。 1个x轴 画线段1和线段3, 第2个x轴 画线段2和线段4.
这问题叫啥？ 挺像 assignment problem. 又不一样... | e****e
发帖数: 418 | | j*****y
发帖数: 1071 | 3 这就是clrs上讲的分配教室，用的 greedy method
4.
【在 j*****n 的大作中提到】
: 有 n 个 线段， 每个线段表示为 [ x_start_n, x_end_n ]. 然后我想把所有这些线
: 段都map到 x axis 上， 但不能互相有 overlap. 问题就是最少开几个 x 轴能把这些
: 线段都map上来， 但互相不能有overlap。
: 比如:
: 线段1:［1, 3]
: 线段2: [ 2, 4]
: 线段3: [ 3, 5]
: 线段4: [4, 6]
: 我最少可以map到2个 x 轴上。 1个x轴 画线段1和线段3, 第2个x轴 画线段2和线段4.
: 这问题叫啥？ 挺像 assignment problem. 又不一样...
| j*****n
发帖数: 1545 | 4 greedy 能保证最优么。 我去查查 CLRS | p*****2
发帖数: 21240 | 5 我昨天也感觉greedy，但是不知道能不能一定最优。jetchen看了之后update一下吧。 | m******s
发帖数: 165 | 6 greedy
事实上，假设最多overlap的地方被k条线段覆盖，则k个x轴必须且足够。
4.
【在 j*****n 的大作中提到】
: 有 n 个 线段， 每个线段表示为 [ x_start_n, x_end_n ]. 然后我想把所有这些线
: 段都map到 x axis 上， 但不能互相有 overlap. 问题就是最少开几个 x 轴能把这些
: 线段都map上来， 但互相不能有overlap。
: 比如:
: 线段1:［1, 3]
: 线段2: [ 2, 4]
: 线段3: [ 3, 5]
: 线段4: [4, 6]
: 我最少可以map到2个 x 轴上。 1个x轴 画线段1和线段3, 第2个x轴 画线段2和线段4.
: 这问题叫啥？ 挺像 assignment problem. 又不一样...
| j*****n
发帖数: 1545 | 7 查了一下， 类似于 activity selection problem.
http://en.wikipedia.org/wiki/Activity_selection_problem
是 greedy, 也能保证最优。和我的问题差别就是我需要重复调用直到全部都分配完。 | j*****n
发帖数: 1545 | 8 smart ~!@@
【在 m******s 的大作中提到】
: greedy
: 事实上，假设最多overlap的地方被k条线段覆盖，则k个x轴必须且足够。
:
: 4.
|
|
