0
$\begingroup$

Question: You are given a set of events in a day. Each event has a start and end time. Find the maximum number of concurrent events

Solution:

  1. First convert events into an array of "Event objects". Each object has a Time field and EventType(start/End) field. (O(N)

  2. Min-heapify the array, with time as the key to order the elements. O(N)

  3. Until heap is empty, do a removeMin(). if event is start increment numConcurrent, if it is a end decrement numConcurrent. Keep track of max value of numConcurrent. O(N*Logn)

SO, complexity is O(N * logN). Is this analysis correct? The interviewer told me thatI need to do it using sort to get O(N*logN). I don't see why because above solution achieves the same.

$\endgroup$
  • $\begingroup$ Putting everything in a heap and then extracting everything is sorting. I don't understand what your interviewer meant. Note that since calendars usually store events with (at best) minute precision, you can use a linear sorting algorithm. $\endgroup$ – adrianN Jul 22 '16 at 8:31
  • $\begingroup$ 1) I don't see how this algorithm solves the problem. 2) Do you have a conceptual question? Just checking your solution does not make a good question. $\endgroup$ – Raphael Jul 22 '16 at 14:20
  • $\begingroup$ Can you comment on why the solution is incorrect? $\endgroup$ – Smart Home Jul 23 '16 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.