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!

  • 1
    $\begingroup$ Do you have a question? We are a question-and-answer site, so we require you to articulate a specific question. Please ask the question in the body of your post. $\endgroup$ – D.W. Jun 5 at 6:41
  • $\begingroup$ I encourage you to refer to our general guidance on dynamic programming problems (cs.stackexchange.com/tags/dynamic-programming/info), follow the systematic approach outlined there, and show us what progress you've made. $\endgroup$ – D.W. Jun 5 at 6:42
  • $\begingroup$ @D.W. thank you for the source you mentioned. I am confused about the way I should approach this problem? I think dynamic programming might help here but I am not sure of it since the addition of a new day can change earlier window groupings. The new element can be min( cost(upgraded cost if it is added in the old interval), cost(new interval is started), cost(old interval size is changed)) at each step which makes me think it is backtracking. I have edit the post to ask the question. $\endgroup$ – Mihir Jun 6 at 14:27
  • $\begingroup$ Try to find a recursive algorithm, as explained at those links. Check the candidate ways to form a set of subproblems, as explained at those links. $\endgroup$ – D.W. Jun 6 at 18:59
  • $\begingroup$ I found this leetcode problem with identical problem statement. Thank you again for your help $\endgroup$ – Mihir Jun 7 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.