Minimize batches and allocate riders by time

Problem Statement

You are managing a delivery platform and have a list of delivery requests. Each request has a delivery time window [start_time, end_time] and a required capacity c. You have a fleet of delivery batches, where each batch has a maximum capacity K.

A batch can handle multiple deliveries if their time windows are compatible (they can be performed concurrently) and the sum of their required capacities does not exceed K. Two delivery requests are compatible if their time intervals [s1, e1] and [s2, e2] allow them to be processed together. For this problem, assume two requests are compatible if their time windows overlap. However, to keep it simple, we define a batch as a set of requests that can all be performed within a single common time period, provided the total capacity constraint K is met.

Given a list of requests requests = [[start, end, capacity], ...] and a batch capacity K, return the minimum number of batches required to fulfill all deliveries.

Function Signature

def min_batches(requests: List[List[int]], K: int) -> int

Constraints

• 1 <= len(requests) <= 10^4
• 0 <= start < end <= 10^6
• 1 <= capacity <= K
• 1 <= K <= 100

Example 1

Input: requests = [[1, 5, 2], [2, 6, 2], [7, 8, 1]], K = 3 Output: 2 Explanation: The first two requests overlap and have a total capacity of 4, which exceeds K=3, so they must be in different batches. The third request can share a batch with either.

Edge Cases

• Single request.
• All requests have the same time window.
• Total capacity of overlapping requests exactly equals K.