# Least Money to Buy Bus Tickets

• There're 3 kinds of bus ticket.
1: ticket 1 cost 2 and can be used for a day.
2: ticket 2 cost 7 and can be used for a consecutive 7 days.
3: ticket 3 cost 25 can be used for a month. Assume month here means 30 consecutive days.

Now there's a array filled with elements. Each element value is a date for a person to travel. This array has already been sorted in ascending order, like {1,3,4,5,11,12,23,24,30}.
Obviously the final day is 30th and first day is 1st.

So for any given array from a person to travel, how can this person cost least ?

Example:
given array like
int [] arr={1,3,4,5,6,7,12,13,14,15,16,17,18,19,20,28,30};
the least cost is 22, for 1~7 days cost 7, 12~18 days cost 7, and 19,20,28,30 each costs 2 so it sums up to be 22.

• This post is deleted!

• @1337c0d3r hey i know the answer to the question i post, is there any way i can submit it and this leetcode can automatically check it for me

• public class Solution {

public static void main(String[] args) {
int [] arr={1,3,4,5,6,7,12,13,14,15,16,17,18,19,20,28,30};
int total = new Solution().solution(arr);
System.out.println("total count: "+total);
}
public int  solution(int[] arr) {
int len=arr.length;
System.out.println("lenght of this array: "+len);
if(len<4){
return 2*len;
}
if(len>=4&&len<23){
return checkForSevenDayTicketChoice(arr, len);
}
if(len>=23&&len<=30){
int total=0;
int i=0;
while(i<len){
int startIndex=i;
int twenty9DaysAfter=arr[i]+29;
if(i<=len-1-22&&arr[i+22]<=twenty9DaysAfter){
System.out.println(" from date="+arr[i]+" to "+arr[i+22]+" should choice 30 day ticket");
total+=25;
i=i+23;
while(i<len&&arr[i]<=twenty9DaysAfter&&i<=startIndex+29){
System.out.println(" date="+arr[i]+" still within range of 30 days");
i++;
}
}else{
return checkForSevenDayTicketChoice(arr, len);
}

}
return total;
}
return -1;
}
private int checkForSevenDayTicketChoice(int[] arr, int len) {
int total=0;
int i=0;
while(i<len&&(len>=4||len<23)){
int startIndex=i;
int sevenDaysAfter=arr[i]+6;
if(i<=len-1-3&&arr[i+3]<=sevenDaysAfter){
System.out.println(" from date="+arr[i]+" to "+arr[i+3]+" should choice 7 day ticket");
total+=7;
i=i+4;
while(i<len-3&&arr[i]<=sevenDaysAfter&&i<=startIndex+6){
System.out.println(" date="+arr[i]+" still within range of 7 days");
i++;
}
if(i==len-1){
break;
}
}else{
System.out.println("now date="+arr[i]+" use 1 day ticket");
total+=2;
i++;
}
}
return total;
}

}

• I like the tickets and Ticket to ride, but the problem here sounds different. My solution used dynamic programming and greedy technics.
Don't claim to be the best,, expect improvement.
Idea : MinCost[i] = min minCost[j - day] + val , subject to day = 1,7, 30, val = 2,7,25 . If i is day when user doesn't travel then find the latest day before this day and solve the problem for it.
Ofcourse I agree that it is better to ve solved only with greedy.

P.S Itried with greedy , there are cases in wich greedy is not optimal, for example :[1, 6, 9, 11, 16, 20, 21, 22, 24, 25], greedy returns 19, dp - 17

int minBusTickets(int[] trips, int[] cost, int day, int lastIndex) {
if (day < trips[0])
return 0;
if (cost[day] > 0)
return cost[day];
int l = 0;
int r = lastIndex;
while (l <= r) {
int mid = l + (r - l)/2;
if (trips[mid] == day) {
lastIndex = mid;
break;
}
else if(trips[mid] < day)
l = mid + 1;
else
r = mid - 1;
}

if (l > r) {
day = trips[r];
lastIndex = r;
}

int min = Integer.MAX_VALUE;
min = Math.min(min, minBusTickets(trips, cost, day - 1,lastIndex) + 2);
min = Math.min(min, minBusTickets(trips, cost, day - 7,lastIndex) + 7);
min = Math.min(min, minBusTickets(trips, cost, day - 30,lastIndex) + 25);
cost[day] = min;
return min;

}

• Hi

Can somebody please provide the problem number in LeetCode? I want to practice this very problem.

Thanks
Satvir

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.