Editorial for Wesley's Anger Contest 2 Problem 2 - Costume Shopping
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
To use a minimum amount of money to buy all the costumes, taking a greedy approach and buying the cheapest costume available for the day until we have costumes will give us the correct answer.
To do this efficiently we can represent the entire days as
intervals of time, each spanning over some days until the next price change. By processing these
intervals of time using the price from least to greatest, we can efficiently find the best days to buy costumes.
Special care must be given to adjacent intervals which intersect on their endpoints. Using a set or map will suffice for taking care of this case.
Time Complexity:
Comments