THE QUESTION:
There is an event where there are N contestants. There are three tasks in the event: A,B,C (say). Each participant takes part in the events in the listed order: i.e a contestant must first complete A and B before beginning C.
However, in event A only one person can participate at a time. Any number of people may simultaneously participate in B and C.
So the event works as follows. At time 0, the first contestant begins A, while the remaining citizens wait for the first person to finish. As soon as the first person is done, he or she proceeds to event B, and the second citizen begins A. In general whenever a person completes A, the next person begins A. Whenever a person is done with A, he or
she proceeds to B immediately, regardless of what the other contestants do. The whole event ends as soon as all the contestants finish all 3 events.
So the basic question is given the number of participants N, and the time taken by each person for each of the 3 events, calculate the minimum time in which the whole event might be completed.
MY ATTEMPT:
This is the algorithm I came up with:
LeastTime(people (2d array [n][3] with time of each person for each event, n, front_chosen = false)
The least time for n people can be broken up into 2 cases:
1. The current guy seated first for event A
1.1 We take t1_1 -> time for current guy in event A + time taken for the rest of the people to finish the whole event with the front taken
1.2 We take t1_2 -> time for current guy in event A + time for his remaining events
1.3 The time taken for the whole event in this case is t1 = max{t1_1,t1_2}.
2 The current guy is not seated first for event A
2.1 We modify people such that the first element is placed last
2.2 t2 -> LeastTime(people, n, false)
3. We return min {t1,t2}
So that is what I came up with. What are some better i.e more efficient solutions? Even Alternate Solutions will be helpful.
4
Given the time taken by all participants in all events, the time spent on event A is invariant; therefore, the shortest possible overall event duration can be found by focusing on the person who is slowest at the combination of B+C and optimizing the event A ordering to maximize the overlap between (B+C) time and (A) time.
Reorganize input into person[n][2] where Person N’s time on event A is in person[N][1] and their time on events B and C combined is in person[N][2].
Sort descending on column 2 and then on column 1.
The time at which each person finishes is then the sum of all A’s up to and including their own A, plus their BC.
The time at which the event ends is the maximum of the finishing times.
e.g. for people who have times of:
(A,B,C)
[1,2,3]
[2,2,2]
[1,5,6]
[5,1,1]
[4,5,6]
reorganize into:
(A,(B+C))
[1,5]
[2,4]
[1,11]
[5,2]
[4,11]
sort into:
[4,11]
[1,11]
[1,5]
[2,4]
[5,2]
Then finish times are:
4 + 11 = 15
4 + 1 + 11 = 16
4 + 1 + 1 + 5 = 11
4 + 1 + 1 + 2 + 4 = 12
4 + 1 + 1 + 2 + 5 + 2 = 15
And the earliest possible completion of the event overall is 16 minutes.
0