Lease renewal status
A lock service hands one worker a lease at time grant_ms, and the lease covers the ttl_ms milliseconds that follow, so it lapses at grant_ms + ttl_ms. The worker keeps it alive with renewals. renew_times holds the arrival time of each renewal in arrival order, non-decreasing, and never earlier than grant_ms. A renewal that arrives strictly before the current expiry is accepted and sets a new expiry at that arrival time plus ttl_ms, because the window restarts from arrival rather than extending the old one. A renewal that arrives at the expiry or later is refused: the lease has already lapsed and the service has handed it to somebody else, so every renewal after that is refused too. Return a list holding, for each renewal in order, the expiry it produced, or -1 when it was refused.
lease_renewal_expiries(grant_ms: int, ttl_ms: int, renew_times: list[int]) → list[int][1000,500,[1200,1600,1900]]out[1700,2100,2400][0,100,[99,199,200,250]]out[199,-1,-1,-1][7,3,[8,9,12,13]]out[11,12,-1,-1]State 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.
[1000,500,[1200,1600,1900]][1700,2100,2400]not run yetsample[0,100,[99,199,200,250]][199,-1,-1,-1]not run yetsample[7,3,[8,9,12,13]][11,12,-1,-1]not run yetsample