1
$\begingroup$

what algorithm would you use to solve this problem which I recently faced in an interview?

There's a council where people go to have meetings. A person comes at time x and needs to be in a meeting for duration y. The council has a set number of meeting rooms where 1 meeting room can only host one meeting/person. You need to calculate the earliest time that all meetings have been completed.

You are given 3 arguments:

  1. A list of arrival times (this list is not sorted).
  2. A list of durations (this has the same length as the arrival times and both are indexed the same, e.g. if for arrivals[0] the duration will be durations[0])
  3. The number of rooms available.

My solution was:

  1. Sort the arrival times ASC whilst keeping their relation to their corresponding duration.
  2. Create a priority queue that holds the rooms and is sorted by their earliest availability (e.g. the first out will be the next available room).
  3. For each person (e.g arrival): a) get the next available room from the queue (pop); b) calculate when the room will be next available given the person arrival time and duration and c) add the room back to the queue.
  4. return the last item of the queue which holds the room with the latest availability.

My solution worked but wasn't good enough as I didn't proceed with the next interview stages.

$\endgroup$
3
  • $\begingroup$ maybe your solution was not the problem with not moving further. Sounds good to me, $\endgroup$
    – Nikos M.
    Sep 22, 2021 at 15:13
  • $\begingroup$ Maybe they expected candidates to define the problem kind and also possible heuristics to use; ie, u could've said like processor job scheduling/bank or supermarket cashiers. there are different possible priority strategies like shortest job first,....then say I'm going to write a solution based on 1st come 1st served. For ex. u could've assigned a room for very short interviews till they finish, calculate waiting time for strategies since durations are known in advance then apply the one that minimize av./max waiting time $\endgroup$
    – ShAr
    Sep 22, 2021 at 18:12
  • $\begingroup$ It would be better to ask a question with a more clearly specified set of requirements. "What would you use?" calls for opinions and does not indicate any objective criteria for how answers should be evaluated -- see our help center. $\endgroup$
    – D.W.
    Sep 24, 2021 at 5:33

1 Answer 1

3
$\begingroup$

The problem is equivalent to job scheduling problem on parallel machines. The problem is $\mathsf{NP}$-hard even when the arrival time for each job/person is $0$ and the number of machines (or meeting rooms) are $2$.

The $\mathsf{NP}$-hardness proof simply follows from the partition problem.

More precisely, your problem is equivalent to $P;m|rj|C_{max}$, i.e.,

  1. P: Parallel identical machines. Processing time of job $j$ is $p_j$, independent of the machine.
  2. m: Fixed number of machines $m$.
  3. $r_j$: Job $j$ cannot be scheduled before given release time $r_j$.
  4. $C_{max}$: also called Makespan. The maximum completion time over all jobs. The goal is to minimize $C_{max}$.

You can explore related papers in scheduling complexity zoo.

$\endgroup$

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.