A man has to travel for given number of days by bus. He can buy either:

  • $1$ day ticket for $2Rs$ (valid for 1 day)
  • $7$ days ticket for $7Rs$ (valid for 7 consecutive days)
  • $30$ days ticket for $25Rs$ (valid for 30 consecutive days)

We are given an array, whose elements are the day numbers on which he travels.

For example, if the given array is $\{1,3,5,8,9,10\}$, then he travels on these $6$ days. Now we have to minimize the cost of his travel. What would be the best approach to solve this problem?

  • 4
    $\begingroup$ What have you tried? Where did you get stuck? By the best approach do you mean the fastest one? Where have you encountered this problem? $\endgroup$ – Evil Jun 18 '16 at 20:14
  • 1
    $\begingroup$ I tried with grouping them week wise and month wise .So now,i know how many days a man travels in a week or a month starting from a particular day . For Example ,if i chose day number 1 (array index 0 or a[0]) .then the man travels for only 3 days in that week (day 1 ,day 3, day 5) and 6 days in the month (day 1 ,day 3, day 5,day 8 ,day 9, day 10). So ,like this i will come up with the complete information about all the weeks and months .Then i need a way to use this info to calculate minimum cost .I am stuck at this point. Any kind of help would be highly appreciated. $\endgroup$ – Piyush Verma Jun 19 '16 at 6:34
  • 1
    $\begingroup$ If you assign all the costs greedy you may not come to the optimal solution. In given example you can assign $1$ day tickets to everyday (let me call it the bound). It costs $12Rs$. But buying one $7$ day ticket gives you $11Rs$. In that case $30$ day ticket is out. But I assume some bigger array may come in. Do you know dynamic programming? Minimum cost problem? $\endgroup$ – Evil Jun 19 '16 at 16:26
  • 1
    $\begingroup$ If you could address the questions from comments - change title, describe where it came from, edit the question instead of comment it would be nice. Also it is important whether you need it solved (like brute force or backtracking) which works good for small data or have bigger data or want to understand how to model such problems - it changes a lot. Also if this comes from some homework assignment - you should follow presented techniques and read the materials - the answer should be there. Otherwise you can end up in doing some good technique, but not the one required and it will not help. $\endgroup$ – Evil Jun 19 '16 at 16:33

There's a rather simple algorithm for this.

You start at the end of the array, day 10. If you only wanted to travel from that day onwards, you could buy a 1 day, 7 day, or 30 day ticket. 1 day is optimal at a cost of 2.

Then you check the second to last entry, day 9. If you only wanted to travel from that day onwards, you could buy a 1 day ticket (and add the optimal combination of tickets from day 10 at cost 2, total cost = 4), or a 7 or 30 day ticket, which is more expensive.

Again from day 8, the cheapest is a day ticket plus the optimal combination from day 9 on, total cost 6. But then you check day 5: If you buy a single day ticket, you pay 2 plus 6 for travel from day 8, total 7. But if you buy a weekly ticket, the cost is only 7. You then proceed to the beginning of the array.

int n = 6;
int dates [n+1] = { 1, 3, 5, 8, 9, 10, infinity };
int ticket [n];
int cost [n+1];

cost [n] = 0;

for i = n-1 downto 0
    cost for 1 day = 2 + cost [i+1]
    let k7 = smallest k where dates [k] ≥ dates [i] + 7
    cost for 7 day = 7 + cost [k7]
    let k30 = smallest k where dates [k] ≥ dates [i] + 30
    cost for 30 days = 25 + cost [k30]

    if cost for 1 day is smallest
        ticket [i] = 1
        cost [i] = cost for 1 day
    else if cost for 7 day is smallest
        ticket [i] = 7
        cost [i] = cost for 7 days
        ticket [i] = 30
        cost [i] = cost for 30 days

That's easily done in O (n) for any fixed number of different tickets. The answer would be a bit different if you have "weekly" tickets that are valid from Monday to Sunday, or from Sunday to Saturday, depending on the country, and "monthly" tickets that are valid from the 1st to the last day of a month.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.