In the given solution, the provided time complexity is O(nlogk). However, the actual time complexity should be nklog(nk) because all timeslots of each employee’s time slots are added. Therefore, it sorts based on the nk size of results instead of k employees(1 timeslot/employee).
Could you confirm the most optimal time complexity and explain why the heap size is k instead of nk, please?
Thanks,
Grace
Hello @Linda_He,
Thank you for your feedback. Let’s look at why the time complexity of this solution is O(n log k), where n represents the total number of intervals across all employee schedules, and k represents the number of employees.
The solution effectively utilizes a heap to manage the upcoming intervals of each employee. The heap size is k, not nk, as only the start time of each interval is stored. This approach ensures efficient retrieval of the earliest interval for processing.
Therefore, the optimal time complexity is O(n log k) instead of O(nk log(nk)).
Hope this clears your confusion. If you have any further questions, please feel free to ask.
Regards,
Dian