H***e
发帖数: 476 | 1 有一点类似。 据说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 | l******u
发帖数: 1174 | 2 #1: Here is my idea:
Divide the non-covered area into non-overlapping rectangles, say:
L = {B1, B2, ..., Bn}
The total covered area would be total area of the table minus the sum of B1,
B2, ..., Bn. When there is no card on the table, L = {Table}, i.e., the
only rectangle is the table itself.
Drop the cards one by one. For each card Ci, there are several scenarios
where it can relate to each rectangle, Bj:
1. The card Ci does not touch Bj.
==> ignore it.
2. The card Ci contains Bj properly
==> remove Bj from L.
3. The card Ci has 1 corner in Bj
=> Bj will be decomposed into 4 smaller rectangles, 1 of which would be
covered by Ci, the rest 3 will replace Bj in L. Illustrated as follows:
+------------########
| ########
| 1 ##card##
| ########
+------------########
| | |
| | |
| | |
| 2 | 3 |
| | |
| | |
+-------------------+
4. The card Ci has 2 corners in Bj
=> Bj will be decomposed into 6 smaller rectangles, 1 of which would be
covered by Ci, the rest 5 will replace Bj in L. Illustrated as follows:
+------------+------+
| 1 | 2 |
| | |
+------------########
| ########
| 3 ##card##
| ########
+------------########
| | |
| 4 | 5 |
+------------+------+
5. The card Ci has 4 corners in Bj
=> Bj will be decomposed into 9 smaller rectangles, 1 of which would be
covered by Ci, the rest 8 will replace Bj in L.
The key function would be to divide a rectangle by 1 point, or 2 points, or
4 points and find the smaller rectangles not covered. Should be
straightforward.
may
【在 H***e 的大作中提到】
: 有一点类似。 据说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).
| z****c
发帖数: 602 | 3 One idea to solve 1:
Add horizontal intervals and vertical intervals into two interval trees. (
nlogn)
Add the top edge and bottom edge coordinate of cards into an array, sort it.
then you have 2n coodinates and 2n-1 intervals.(nlogn)
Do the same to left and right edge. (nlogn)
All horizontal interval and vertical interval will divide plane into (2n-1)(
2n-1) sub regions.
for each sub region, query two interval trees and find intersection in the
results. You can use a map to find the intersection, which is a O(1) time.
Total time is O(n^2*logn) | i***h
发帖数: 12655 | 4 第二题是图论题?
每个线段是图上顶点, 带权重.
有重叠的两个线段间有边相连.
然后求顶点的子集.
没想好怎么弄 | i***h
发帖数: 12655 | 5 第一题好象先对牌X-Y排序,
然后从左到右扫描一遍
O(n) |
|
