Request Scheduler: Minimum Threads for Concurrent Processing

Problem Context

Groww's backend receives thousands of concurrent user requests every second — from stock price lookups to order placements. Unlike a single process (which has its own memory space and runs independently), threads share the same process memory and can handle tasks concurrently within that process. To efficiently serve users, Groww's backend uses a thread pool where each thread handles one request at a time.

You are given a list of user requests, each defined by their arrival time and processing duration (in milliseconds). Your task is to determine the minimum number of threads needed so that no request ever has to wait — every request is immediately picked up by an available thread upon arrival.

Problem Statement

Given n requests with their arrival times and processing durations, find the minimum number of threads required to handle all requests without any request waiting.

Input Format

• An integer n — number of requests
• A 2D array requests of size n x 2 where:
  • requests[i][0] = arrival time of the i-th request (in ms)
  • requests[i][1] = processing duration of the i-th request (in ms)

Output Format

Return a single integer — the minimum number of threads needed.

Examples

Example 1

Input: requests = [[0,5],[2,3],[4,2],[8,1]] Output: 2 Explanation:

• Thread 1 picks up request at t=0, finishes at t=5.
• Request at t=2 arrives while Thread 1 is busy → Thread 2 picks it up, finishes at t=5.
• Request at t=4 arrives, Thread 2 is still busy (until t=5), but Thread 1 finishes at t=5... wait, at t=4 both are busy → we need a 3rd thread? No — Thread 2 finishes at t=5, Thread 1 finishes at t=5. At t=4 both are busy so Thread 3 is needed... Actually both Thread 1 (busy until 5) and Thread 2 (busy until 5) are occupied at t=4, requiring Thread 3. But Thread 3 finishes at t=6. The max concurrent overlap is 2 at times [2,4], so the answer is 2 threads if we track overlaps carefully using a min-heap of end times.

Example 2

Input: requests = [[0,10],[0,10],[0,10]] Output: 3 Explanation: All 3 requests arrive simultaneously at t=0. Each needs its own thread since no thread is free. Minimum threads = 3.

Example 3

Input: requests = [[0,2],[3,2],[6,2]] Output: 1 Explanation: Requests arrive sequentially and each finishes before the next arrives. A single thread handles all requests one by one.