You are given a list of days numbered 0 to 365 in the calendar year where you need to be in a hotel. You need to book in advance for the year and need not necessarily be there when you have a booking. You can also book only in fixed intervals of 1, 7, 15, or 30 days. You have to be find the minimum cost of booking to stay there on the required days. The stay is cost efficient for longer intervals. (i.e. booking for 7 days at once is cheaper than booking 1 day seven times and so on).
The costs can be assumed to be something like
1: 100 7: 600 15: 1100 30: 2000
However, picking the biggest window size (greedy) does not necessarily give the best solution.
For example for
days = [1, 2, 5, 7, 14, 28] having two intervals of 7 and 15 days is the cheaper option compared having one 30 day interval.
Any help on how to approach this question would be great. Thanks!