diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_time_complete_trip.cpp | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'min_time_complete_trip.cpp')
-rw-r--r-- | min_time_complete_trip.cpp | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/min_time_complete_trip.cpp b/min_time_complete_trip.cpp new file mode 100644 index 0000000..2e325a2 --- /dev/null +++ b/min_time_complete_trip.cpp @@ -0,0 +1,36 @@ +// 2187. Minimum Time to Complete Trips +#include "leetcode.h" + +/* + * given array 'time' where 'time[i]' denotes the time taken by the 'i'th bus to + * complete one trip. each bus can make multiple trips successively; that is, + * the next trip can start immediately after completing the current trip. also, + * each bus operates independently; that is, the trips of one bus do not + * influence the trips of any other bus. also given an integer 'totalTrips', + * which denotes the number of trips all buses should make in total. return the + * minimum time required to complete all trips. + */ + +class Solution { +public: + long long minimumTime(vector<int> &time, int totalTrips) { + long long l = 0, r = LLONG_MAX / time.size(); + while (l < r) { + long long m = (l + r) / 2, trips = 0; + for (int t : time) + trips += m / t; + if (trips < totalTrips) + l = m + 1; + else + r = m; + } + return l; + } +}; + +int main() { + Solution obj; + vector<int> t1 = {1, 2, 3}, t2 = {2}; + printf("%lld\n", obj.minimumTime(t1, 5)); // expect: 3 + printf("%lld\n", obj.minimumTime(t2, 1)); // expect: 2 +} |