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 thanks bro
1 Like