Quick Overview

This question evaluates understanding of interval overlap reasoning, resource-allocation and scheduling concepts, and proficiency with algorithmic complexity and appropriate data structure choices.

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.

Overview: This question evaluates understanding of interval overlap reasoning, resource-allocation and scheduling concepts, and proficiency with algorithmic complexity and appropriate data structure choices.

Read the full TripStack Software Engineer interview experience this question came from

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

  1. Sort intervals by start time and use a min-heap of current end times.
  2. Before placing a new task, pop all end times <= its start (no overlap at equal endpoints).
  3. The heap size after insertion is the number of servers currently used; track the maximum.
  4. Alternatively, use a sweep-line over sorted (time, type) events where end events are processed before start events at the same time.

Loading coding console...

Show the approach

Approach

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)