Find machine shortage
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.
unserved_job_minutes(job_starts: list[int], job_ends: list[int], lease_starts: list[int], lease_ends: list[int]) → int[[0],[10],[],[]]out10[[0,5],[10,15],[0,10],[5,20]]out10[[0,0],[10,10],[0],[10]]out10State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[0],[10],[],[]]10not run yetsample[[0,5],[10,15],[0,10],[5,20]]10not run yetsample[[0,0],[10,10],[0],[10]]10not run yetsample