2

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
  • I think the trick here is you just need to know the time, not the order itself. So it would be something close to sum(A) + min(B+C), with some special case handling.
    – Sign
    Sep 13, 2013 at 15:42
  • @Sign I don't see how that would lead to the solution. Why would we need to do min(B+C)?
    – Anamaki
    Sep 13, 2013 at 15:49
  • That would represent the time for the last person to do task A to complete tasks B and C which would be after everyone else did A (Sum(A)) and you would want the person who does B+C last to be the fastest at it. Then the special case stuff to handle something like the fastest at B+C taking 2 units and everyone else taking 100 units.
    – Sign
    Sep 13, 2013 at 16:07
  • A dependency graph will explain this answer much better. This question is a thought-exercise in parallelization, and frankly doesn't need to involve coding.
    – rwong
    Sep 13, 2013 at 19:54

1 Answer 1

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.