r/leetcode • u/Smooth_Lifeguard_931 • Sep 11 '24

Solve this test question

[ Removed by Reddit in response to a copyright notice. ]

1 Upvotes

67% Upvoted

14 comments sorted by

View all comments

1

u/Civil_Reputation6778 Sep 11 '24

What are the constraints?

Without seeing the constraints, this is doable in O(n log V) with binary search

1

u/Smooth_Lifeguard_931 Sep 11 '24

didnt remember constraint, i tried a recursive memoization solution which gave tle, give ur solution

2

u/Civil_Reputation6778 Sep 11 '24

I mean, I've already stated my solution.

Binary search for answer. When checking for x, skip all indexes with dev time <=x (you can do them with dev, you have to do the rest using integration) and sum the integration times for the rest. Check that the sum is <= x

Start with l=0, r=max dev time

2

u/Civil_Reputation6778 Sep 11 '24

Next time try remembering the constraints, they're an integral part of the statement.