Loading page…
Practice problem · hard
An ad platform runs campaigns. Each campaign is live from its first day to its last day, both days included. Campaigns overlap, and a short campaign is usually more specific than a long one that covers the same day.
For a list of days, the team wants to know which campaign is the most specific. For each day, find the length of the shortest campaign that is live on it.
Write tightest_campaign(campaigns, queries).
campaigns[i] = [first, last], with first <= last. Its length is last - first + 1 days.queries[j], find the shortest campaign with first <= queries[j] <= last, and give its length.Input: campaigns = [[1, 4], [2, 4], [3, 6], [4, 4]], queries = [2, 3, 4, 5]
Output: [3, 3, 1, 4]Process the days in increasing order. For each day, add the campaigns that have started, remove the ones that have ended, and take the shortest of those that remain.
| Day | Live campaigns (length) | Shortest |
|---|---|---|
| 2 | [1, 4] (4), [2, 4] (3) | 3 |
| 3 | [1, 4] (4), [2, 4] (3), [3, 6] (4) | 3 |
| 4 | the same three, and [4, 4] (1) | 1 |
| 5 | [3, 6] (4); the others have ended | 4 |
Input: campaigns = [[2, 3]], queries = [5, 3]
Output: [-1, 2]The queries are not in order. On day 5 the campaign has ended. On day 3 it is live, and its length is 2 days.
Input: campaigns = [[1, 1]], queries = [1]
Output: [1]A one-day campaign has length 1, not 0.
0 ≤ campaigns.length ≤ 50,0000 ≤ queries.length ≤ 50,0001 ≤ first ≤ last ≤ 1,000,000,000, and 1 ≤ queries[j] ≤ 1,000,000,000 (days)Checking every campaign for every day costs about n × q, which is 2.5 × 10^9 at n = q = 50,000. Sorting costs about (n + q) log (n + q), and a heap that holds the live campaigns answers each day in log time.
tightest_campaign · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.