How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Compute minimum servers for cyclic tasks

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of tasks running on servers. Each task is represented as a pair `(start, duration)`: - `start` is the start time in **minutes from the start of a day**, where `0 <= start < 1440`. - `duration` is the runtime in minutes (`duration > 0`). - A task runs **continuously** once started. - A server can run **at most one task at a time**. - If `start + duration > 1440`, the task **wraps past midnight** into the next day. Durations may be larger than 1440 (spanning multiple days). Return the **minimum number of servers** required so that all tasks can run without overlap on the same server. Clarification: Treat each task as an interval on a real timeline starting at day 0; wrapping means the interval crosses into day 1 (or beyond). Two tasks overlap if their running time intervals intersect. Example: - `tasks = [(1380, 60), (0, 30), (1380, 30)]` - (1380, 60) runs 23:00–24:00 - (0, 30) runs 00:00–00:30 - (1380, 30) runs 23:00–23:30 Expected output: `2`

Quick Answer: This question evaluates understanding of interval scheduling, overlap detection, and handling cyclic time via modular arithmetic for tasks that wrap past midnight, reflecting competency in reasoning about resource allocation on continuous timelines.

You are given a list of tasks running on servers. Each task is represented as a pair `(start, duration)`, where `start` is the minute within day 0 when the task begins, and `duration` is how many minutes it runs continuously. A task occupies the half-open interval `[start, start + duration)`. If `start + duration > 1440`, the task continues into the next day (or beyond). Return the minimum number of servers needed so that no two overlapping tasks are assigned to the same server. If one task ends exactly when another starts, they do not overlap and may use the same server.

Constraints

0 <= len(tasks) <= 200000
0 <= start_i < 1440
1 <= duration_i <= 1000000000
Each task occupies the interval [start_i, start_i + duration_i)

Examples

Input: ([(1380, 60), (0, 30), (1380, 30)],)

Expected Output: 2

Explanation: The tasks at 1380 overlap with each other, so 2 servers are needed. The task from 0 to 30 does not overlap with them.

Input: ([],)

Expected Output: 0

Explanation: No tasks means no servers are needed.

Input: ([(0, 60), (60, 15), (30, 30)],)

Expected Output: 2

Explanation: The first and third tasks overlap on [30, 60). The second starts exactly at 60, so it can reuse a server from a task that ended at 60.

Input: ([(10, 2000), (20, 100), (50, 1000), (60, 10)],)

Expected Output: 4

Explanation: From time 60 to 70, all four tasks are running simultaneously, so 4 servers are required.

Input: ([(0, 1440), (1439, 2), (1439, 1)],)

Expected Output: 3

Explanation: Between 1439 and 1440, all three tasks are active at once, including the ones that wrap past midnight.

Hints

Do not split a wrapping task by day boundaries. Treat every task as one interval on a single increasing timeline: [start, start + duration).
The answer is the maximum number of intervals active at the same time. Sort start/end events and sweep from left to right.

Quick Overview

This question evaluates understanding of interval scheduling, overlap detection, and handling cyclic time via modular arithmetic for tasks that wrap past midnight, reflecting competency in reasoning about resource allocation on continuous timelines.