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)
Solution
from typing import List
import heapq
def min_servers(intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals_sorted = sorted(intervals, key=lambda x: (x[0], x[1]))
heap: List[int] = [] # min-heap of end times
max_used = 0
for start, end in intervals_sorted:
# Free all servers whose tasks ended at or before this start time (half-open)
while heap and heap[0] <= start:
heapq.heappop(heap)
# Ignore zero-length tasks; [t, t) occupies no time
if start < end:
heapq.heappush(heap, end)
if len(heap) > max_used:
max_used = len(heap)
return max_used
Explanation
Sort tasks by start time and maintain a min-heap of end times for tasks currently running. For each task [start, end), pop from the heap all end times <= start; this enforces the half-open rule where an end at t does not overlap a start at t. Then, if the task is non-empty (start < end), push its end time. The heap size is the number of servers in use at that moment; the answer is the maximum heap size seen. Zero-length intervals [t, t) are ignored as they occupy no time.
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.