Give me some hints, please!!!
Can this task be solved using only sorting?
Does the solution always exist?
There's always a solution.
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!
Re: There's always a solution.
Posted by
Xeno 19 Oct 2004 13:29
What's the so called 'odd positions' or 'even positions' please?
Re: There's always a solution.
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.
Re: There's always a solution.
Posted by
Kit 22 Apr 2005 12:48
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.
Re: There's always a solution.
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.
to Kit
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
sorry, I bad read statement
right answer
1
1
Test
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.