返回信息流坐标轴上有两种线段，分别是黑线段和白线段，每种线段若干，其起止点坐标已知。求问如何选出最少的白线段，能够完全覆盖黑线段，如果不能覆盖，指出那条黑线段不能被覆盖。好像是贪婪算法，求解啊
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #92350同步于 2017/3/11
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
互联网公司面试算法题
xueluowuhen
2017/3/11镜像同步11 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
我就是理解成一维的了，每个线段都用<l,r>表示，<lb,rb><lw,rw>表示黑线和白线。首先找到右端点最小的黑色线段，你为了覆盖这条线段就必须找lw <= rb && rw>= lb的这些白线（如果找不到当然这条线就无法覆盖）。为了选出的白线可以覆盖更多黑线，就要找中间有最大的rw值的白线进行覆盖，然后再找未被覆盖的右端点最小的黑线直到选完。应该就是按端点排序后扫一遍
【 在 xueluowuhen 的大作中提到: 】
: 坐标轴上有两种线段，分别是黑线段和白线段，每种线段若干，其起止点坐标已知。求问如何选出最少的白线段，能够完全覆盖黑线段，如果不能覆盖，指出那条黑线段不能被覆盖。好像是贪婪算法，求解啊
应该是lw <= lb && rw>= rb吧
【 在 hlcjj 的大作中提到: 】
: 我就是理解成一维的了，每个线段都用<l,r>表示，<lb,rb><lw,rw>表示黑线和白线。首先找到右端点最小的黑色线段，你为了覆盖这条线段就必须找lw <= rb && rw>= lb的这些白线（如果找不到当然这条线就无法覆盖）。为了选出的白线可以覆盖更多黑线，就要找中间有最大的rw值的白线进行覆盖，然后再找未被覆盖的右端点最小的黑线直到选完。应该就是按端点排序后扫一遍
Ik=< sk , fk > represents white Interval
Jk=< bk , ek > represents black Interval
Classify event e:
e=(sk , w, Ik) white interval activation event (interval activation time = sk)
e=(bk , b, Jk) black interval activation event (interval activation time = bk)
?ActInts = Max Priority Queue of activated intervals Ik [priority = fk ].
?Events = Min Priority Queue of unprocessed events [priority = activation time].
Algorithm OptIntervalIntervalCover (I= {I1 , I2 , … , Im}, J= {J1 , J2 , … , Jn})
1. ; ; ,
2. MakeEmptyMaxHeap(ActInts)
3. Events ? ConstructMinHeap( ) § O(n+m) time
4. while ?do § O(n + m) iterations
5. e ?DeleteMin(Events) § next event to process, O(log(n+m)) time
6. if e = (sk , w, Ik) then Insert(Ik , ActInts) § activate interval
7. else § event e is balck interval
8. if ek>Last then do§ greedy choice 1: < bk, ek >=leftmost uncovered interval
9. Ik ? DeleteMax(ActInts) § greedy choice 2, O(log m) time
10. if fk < ek then return ( Interval(bk, ek) is not covered by I)
11. else do
12. C? C {Ik}
13. Last? fk
14. end-else
15. end-if
16. end-while
17. return ( C )
end
Complexity: O( (n+m) log(n+m) ) time
没看见是完全覆盖，我这个是有覆盖的方案，完全覆盖改一下就行
【 在 xueluowuhen 的大作中提到: 】
: 应该是lw <= lb && rw>= rb吧
【 在 xueluowuhen 的大作中提到: 】
: 坐标轴上有两种线段，分别是黑线段和白线段，每种线段若干，其起止点坐标已知。求问如何选出最少的白线段，能够完全覆盖黑线段，如果不能覆盖，指出那条黑线段不能被覆盖。好像是贪婪算法，求解啊
有题目提交的地方吗？