Loading page…
Practice problem · medium
A payments app runs cashback offers. Each offer can be claimed on any day from its first day to its last day, both included. A user can claim only one offer a day, and each offer can be claimed once.
You get all the offers. Find the largest number of offers the user can claim.
Write most_offers(offers).
offers[i] = [first_day, last_day], with first_day <= last_day.Input: offers = [[1, 2], [2, 3], [3, 4], [1, 2]]
Output: 4Go through the days. On each day, add the offers that start then, forget the offers that have expired, and claim the open offer with the earliest last day.
| Day | Open offers (last days) | Claimed | Total |
|---|---|---|---|
| 1 | 2, 2 | [1, 2] | 1 |
| 2 | 2, 3 | [1, 2] | 2 |
| 3 | 3, 4 | [2, 3] | 3 |
| 4 | 4 | [3, 4] | 4 |
All 4 offers are claimed.
Input: offers = [[1, 1], [1, 1], [1, 1]]
Output: 1All three offers are valid on day 1 only, and one can be claimed per day.
Input: offers = [[1, 5], [1, 1]]
Output: 2Claim the short offer on day 1, because it expires then. Claim the long offer on day 2.
0 ≤ offers.length ≤ 100,0001 ≤ first_day ≤ last_day ≤ 1,000,000,000Trying every choice of day for every offer is exponential. Stepping through every day is not possible when days go up to 10^9. Sorting costs n log n, and a heap of open offers costs log n per offer.
most_offers · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.