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
First convert events into an array of "Event objects". Each object has a Time field and EventType(start/End) field. (O(N)
Min-heapify the array, with time as the key to order the elements. O(N)
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.