UVA 11389 and the Greedy Method for Load Balancing
UVA 11389: The Bus Driver Problem
Solution: Sort the arrays of morning times and evening times in opposite orders: sort morning times from least to greatest and evening times from greatest to least. Now, if we transpose (merge) the sorted arrays into one array, we can apply the greedy load balancing algorithm, by pairing numbers from opposite ends. Note that all numbers can be paired together since we have an equal amount of elements in the morning time array and night time array.
The original greedy load balancing algorithm is optimal because the X-th smallest element is always paired with the X-th largest element. This, however, cannot be recreated here since there is an additional restriction: the pairs must include exactly one morning element and exactly one evening element. Hence, we have an "almost-sorted" array, from (pseudo) least to greatest, which looks like this (sample test case):
morn night
10 15 | 10 15
Now, if we start from opposite ends of the array, we can optimally pair the morning and nighttime elements.
This is an in-theory explanation; of course, we can simplify it by separating the arrays and going forward on one array and going the opposite direction on the other.
Solution: Sort the arrays of morning times and evening times in opposite orders: sort morning times from least to greatest and evening times from greatest to least. Now, if we transpose (merge) the sorted arrays into one array, we can apply the greedy load balancing algorithm, by pairing numbers from opposite ends. Note that all numbers can be paired together since we have an equal amount of elements in the morning time array and night time array.
The original greedy load balancing algorithm is optimal because the X-th smallest element is always paired with the X-th largest element. This, however, cannot be recreated here since there is an additional restriction: the pairs must include exactly one morning element and exactly one evening element. Hence, we have an "almost-sorted" array, from (pseudo) least to greatest, which looks like this (sample test case):
morn night
10 15 | 10 15
Now, if we start from opposite ends of the array, we can optimally pair the morning and nighttime elements.
This is an in-theory explanation; of course, we can simplify it by separating the arrays and going forward on one array and going the opposite direction on the other.
Comments
Post a Comment