|
|
back to boardCan this task be solved using only sorting?
Does the solution always exist?
Denote by L the total length covered by all the intervals.
First delete all those intervals that is completely contained by any other. Then sort the remaining intervals. Now put those that have odd positions into the 1st group, and those with even positions into the 2nd group. Calculate the total lengths covered by each group, and let's call them s1 and s2. If s1>=L*2/3, then the intervals in the 1st group make a solution. If s2>=L*2/3, then the intervals in the 2nd group make a solution. Otherwise, the solution should contain the intervals in both groups, which is easy to prove.
Good Luck! What's the so called 'odd positions' or 'even positions' please? Now you've deleted some of the intervals. Sort the rest according to either the left end or the right end. 'Odd intervals' mean those at positions 1,3,5,7,etc in the sorted sequence, and 'even intervals' mean those at positions 2,4,6,8,etc. What for this test:
0 109
10
0 100
1 101
2 102
3 103
4 104
5 105
6 106
7 107
8 108
9 109?
Your method gives the 1st group (1, 3, 5, 7, 9) and the 2nd groop (2, 4, 6, 8, 10). The 1st does not make a solution, like the second group or join of the 1st and the 2nd. This method really works?
Sorry for my English. The idea is almost correct. Just remove segments which are covered by SOME SUBSET of other segments. I.e. find any chain which covers entire range [T0;T1], but segments i and i+2 do not overlap. Kit 22 апреля 2005 12:48
test:
0 109
10
0 100
1 101
2 102
3 103
4 104
5 105
6 106
7 107
8 108
9 109
The right answer 0? sorry, I bad read statement
right answer
1
1 What if segments i and i+1 haven't crossing?
Smth like that:
----
-----
By your idea, we should divide these sectors into different groups, but it's more effectively to join 'em. |
|
|
