A shop runs discount campaigns. Campaign i is campaigns[i] = [start, end] and runs on every day from start to end, both included, so it lasts end - start + 1 days. Campaigns may overlap and may repeat.
For each day in days, the analytics team wants the length of the shortest campaign running on that day, or -1 if no campaign runs that day.
Write shortest_running(campaigns: list[list[int]], days: list[int]) -> list[int] that returns the answers in the same order as days.
shortest_running([[1, 10], [3, 5], [4, 8], [12, 12]], [4, 9, 11, 12, 0])
# [3, 10, -1, 1, -1]
# day 4: [1, 10], [3, 5] and [4, 8] run; [3, 5] is shortest with 3 days
# day 9: only [1, 10] runs; day 11: nothing; day 12: [12, 12] lasts 1 day
shortest_running([[2, 6], [2, 6], [5, 5]], [5, 6, 5])
# [1, 5, 1] (days can repeat)
Constraints:
1 <= len(campaigns) <= 10^5and1 <= len(days) <= 10^5.0 <= start <= end <= 10^9, and every day is in[0, 10^9].
Checking every campaign for every day is O(n·q), far too slow here. Aim for O((n + q) log(n + q)).
Show hint
you don't have to answer the days in the order they're given. If you visit days from earliest to latest, each campaign becomes relevant once and stops being relevant once; keep the relevant ones where the shortest is always quick to find.