Katkat
Back

Compute minimum servers for cyclic tasks

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage overlapping intervals in a circular domain by converting cyclic tasks into linear sub-intervals and applying a sweep-line or greedy approach to determine resource requirements.

Problem Statement

You are managing a set of tasks that run on a daily 24-hour cycle (0 to 1439 minutes). Each task is defined by a start time S and an end time E (inclusive of S, exclusive of E). If S = E, the task wraps around midnight (e.g., a task starting at 22:00 and ending at 02:00 is represented as [1320, 120]).

Given a list of tasks [[S1, E1], [S2, E2], ...], calculate the minimum number of servers required so that no task is dropped. Assume servers can handle multiple tasks sequentially if one task ends at the same time another begins.

Function Signature

def min_servers(tasks: List[List[int]]) -> int:

Examples

Example 1: Input: tasks = [[100, 200], [150, 250], [50, 120]] Output: 2 Explanation: At time 150, both [100, 200] and [150, 250] are active. We need at least 2 servers.

Example 2: Input: tasks = [[1400, 100], [50, 150]] Output: 2 Explanation: The task [1400, 100] wraps around midnight, covering [1400, 1439] and [0, 100]. This overlaps with [50, 150] during the [50, 100] window.

Constraints

  • 0 <= S, E < 1440
  • Number of tasks: 1 <= N <= 10^5
  • Time complexity should be better than O(N^2).

Hints

Hint 1

Tasks that wrap around midnight can be split into two linear intervals: [S, 1440) and [0, E).

Hint 2

Once you have a list of linear intervals, the problem becomes finding the maximum number of overlapping intervals at any point in time.

Hint 3

Use a difference array or an event-based approach (increment count at start, decrement at end) to find the maximum overlap in O(N log N) time.

Follow-up questions

  • How would your solution change if tasks had specific server affinity, meaning a task must run on a server that has already processed a 'compatible' type of job?
  • If the timeline was not a fixed 1440 minutes but a general time range [0, T], how would you handle very large values of T?
  • What if tasks were not just binary (on/off) but had variable resource requirements (e.g., CPU or RAM)?