问道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问道题

问道题# JobHunting - 待字闺中

j*n2012-12-14 08:12

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*e2012-12-14 08:12

2 楼

greedy吧。

j*y2012-12-14 08:12

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*n2012-12-14 08:12

4 楼

greedy 能保证最优么。我去查查 CLRS