|
|
back to boardShow all messages Hide all messagesCan 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. to Kit Rumter (2) 17 Oct 2008 20:28 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 Rumter (2) 17 Oct 2008 21:27 sorry, I bad read statement right answer 1 1 Test marqueewinq 23 Nov 2011 20:27 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. |
|
|