Katkat

Compute minimum resources for overlapping intervals

TripStackSoftware Engineer · Technical Screen

Last 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.