有一点类似。 据说1是经典题?
1. deck of cards
put them randomly on the table.
two cards can only overlap with rectangle area.(cards must be Vertical/
horizontal to the edge of the table)
find the total area covered by those cards?
2. Given are a set of intervals S = {I1,I2.....In}, each interval have
different positive weight (weight is independent to the interval, there may
be the case that a long interval has a low weight but a short interval has
high weight).
Purpose: Find out a subset of S, say Sub, such that for every interval in S,
there is an interval I in Sub such that they are somehow overlap.
Requirement: the total weight of Sub is minimum.
就是说,找到一部分的interval,使得S内的所有interval和他们(中的某一个interval
)都有交集,并且要求最小的weight