Compute minimum resources for overlapping intervals
TripStackSoftware Engineer · Technical ScreenLast updated
This question evaluates understanding of interval overlap reasoning, resource-allocation and scheduling concepts, and proficiency with algorithmic complexity and appropriate data structure choices.
You are given n tasks as half-open time intervals [start, end) on a single day. Determine the minimum number of identical servers needed so that no two overlapping tasks run on the same server. Design an O(n log n) algorithm and describe the data structure(s) you will use (e.g., sweep line with event sorting or a min-heap of end times). Analyze time and space complexity, explain how you handle equal endpoints (e.g., an end at t and a start at t do not overlap), and discuss edge cases such as an empty list or identical intervals. Optionally, extend your solution to also return one valid assignment of tasks to servers.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.