Compute minimum resources for overlapping intervals
Company: TripStack
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: 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 a list of n half-open intervals [start, end) representing tasks within a single day. Return the minimum number of identical servers required so that no two overlapping tasks run on the same server. Two intervals [a, b) and [c, d) overlap if there exists a time t such that t is in both intervals; therefore, an interval ending at time t does not overlap with one starting at time t. Intervals with start == end are zero-length and require no server. If the list is empty, return 0.
Constraints
- 0 <= n <= 200000
- 0 <= start <= end <= 10^9
- Intervals are half-open: [start, end)
- Target time complexity: O(n log n)
- Space complexity: O(n)
Hints
- Sort intervals by start time and use a min-heap of current end times.
- Before placing a new task, pop all end times <= its start (no overlap at equal endpoints).
- The heap size after insertion is the number of servers currently used; track the maximum.
- Alternatively, use a sweep-line over sorted (time, type) events where end events are processed before start events at the same time.