Question- I think it is of graph
Hii @aman212yadav
It was from a contest on hackerearth
Here is the question
Please solve it
`You are in an amusement park from time 0 to l. There are n types of trains you can play with. Each journey on the ith typeof train lasts d minutes. The ith train have several start times. You can join and exit in the middle of the journey of a train. You never join the same train twice.
Determine the minimum number of times you should join a train to spend all your time.
Note: If you finish a journey at t, then the next journey should be started exactly at t not t+1. You should start exactly at 0 and finish exactly on l.
Input format:
The first line contains n, l.
Each of next n lines contain train d, t where d is the duration of each journey of this train and t is the number of times it starts its journey.
Then t numbers are provided in increasing order. Each number determines a start time for a journey of this train.
Output Format:
Determine the minimum number of times you should join a train to spend all the time. If impossible to spend all time print -1.
Constraints:
1<=n<=20
1<=d<=l<=10^9
1<=c<=1000
Sample Input
4 101
51 3 15 29 55
41 2 0 65
31 2 21 90
19 1 0
Sample Output
3
Explanation:
We should attend the first journey of the fourth train from time 0 to time 19. Then we join the first journey of the first train from time 19 to time 66. Finally, we join the last journey of second train from time 66 to time 101.
it think its a dp problem similar to 0-n knapsack (not sure).
sorry bro , i cant. . . . . . . . . .
Can you suggest someone else who can help?
.
pls ask this doubt again (do mention the problem clrearly),
TA who have solved it earlier will help u.
also if u have problem link then do share it with me.
Should i include some tag or something like that with this problem?
and sorry i don’t have link to the problem
is it from some ongoing contest?
it would tough for someone to solve it without problem link.
btw just mention this complete problem statement in ur doubt description and then raise it.
No it is not from an ongoing competition.
This problem is clinging to me for a very long time and after not getting solution on my own, I turned to cb.
I have posted it again
Thank you so much for your help.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.