Find machine shortage

Write codeMedium25 min

Your task

A render farm queues jobs and rents worker machines by the minute. Job i sits in the queue from job_starts[i] up to but not including job_ends[i], and each waiting job needs one machine for every minute it waits. Lease k supplies exactly one machine from lease_starts[k] up to but not including lease_ends[k]. Both records arrive unsorted, jobs and leases pile up freely on the same minute, and an entry whose bounds match supplies or needs nothing. During any minute the farm falls short by the number of waiting jobs beyond the machines then leased, or by nothing at all when the machines cover them. Minute numbers run from minus 10^9 to 10^9. Return the shortfall summed over every minute.

Examples

unserved_job_minutes(job_starts: list[int], job_ends: list[int], lease_starts: list[int], lease_ends: list[int]) -> int

Example 1

Inputunserved_job_minutes([0], [10], [], [])

Output10

Example 2

Inputunserved_job_minutes([0, 5], [10, 15], [0, 10], [5, 20])

Output10

Example 3

Inputunserved_job_minutes([0, 0], [10, 10], [0], [10])

Output10