Smallest free hub for a task

You run a fleet of n compute hubs, numbered 0 to n - 1, and need to place one new task on a single hub.

You are given:

• capacities: an integer list of length n. capacities[i] is the processing capacity of hub i.
• intervals: a list of n lists of strings. intervals[i] holds the time ranges already booked on hub i, each written "start:end" with integer times. Both ends are inclusive.
• requiredCapacity: the capacity the task needs.
• taskInterval: the task's time range, also "start:end" and inclusive.

A hub can take the task when its capacity is at least requiredCapacity and none of its bookings overlaps the task interval. Because ends are inclusive, two ranges that share even one time unit overlap: a booking "4:6" blocks a task "6:9".

Return the index of the hub that can take the task and has the smallest capacity. If several qualify with the same capacity, return the smallest index. Return -1 if no hub can take it.

find_smallest_hub(capacities, intervals, requiredCapacity, taskInterval) -> int

Constraints: 0 <= n <= 10^5; total bookings up to 2 * 10^5; times fit in a 32-bit integer and start <= end. Bookings on one hub may be unsorted.

Example 1

capacities       = [9, 3, 5]
intervals        = [[], ["0:2"], ["7:8"]]
requiredCapacity = 3
taskInterval     = "1:4"

Hub 1 is busy (0:2 overlaps 1:4). Hubs 0 and 2 are free, and hub 2 has the smaller capacity. Answer: 2.

Example 2

Same hubs, taskInterval = "3:6". Hub 1 is now free and is the smallest that fits. Answer: 1.

Part 2. Requests arrive one after another. Each accepted task is booked on its chosen hub, so it blocks later requests. Design a class with schedule(requiredCapacity, taskInterval) -> int that is fast across many calls.

Reconstructed from the reported question; details may differ from what interviewers ask.