C - Tsundoku


i have tried using stack and simple logic to solve this please tell me why i am getting TLE in this

Actually Greedy Approach won’t work here.
For ex, part where greedy algo fails is
Stack 1 -> 200 1 1 1 1
Stack 2-> 10 11 12 13 14
Try to implement prefix sum array and select the books till position where sum of array elements <= Total time given

1 Like

Use Binary search or 2 pointer.

1 Like

you can refer this both are same question

2 Likes

thanks bro

bro can you explain the reason why this approach fails

Take this test case:
5\;1500
1000 \;1\; 1\; 1\; 1
500\; 500\; 500\; 500\; 500
Now the greedy algo will never pick 1000, this means you’ll only be able to pic 3 books. (All 500).
But if we choose to pic the 1000 book, we can read all the other 1 books, and end up reading 5 books.

2 Likes

got it :love_you_gesture:thanks bro

1 Like