aboutsummaryrefslogtreecommitdiff
path: root/latest_time_catch_bus.py
diff options
context:
space:
mode:
Diffstat (limited to 'latest_time_catch_bus.py')
-rw-r--r--latest_time_catch_bus.py62
1 files changed, 62 insertions, 0 deletions
diff --git a/latest_time_catch_bus.py b/latest_time_catch_bus.py
new file mode 100644
index 0000000..3e1b1a8
--- /dev/null
+++ b/latest_time_catch_bus.py
@@ -0,0 +1,62 @@
+# 2332. The Latest Time to Catch a Bus
+
+"""
+given a 0-indexed array 'buses' of length 'n' where 'buses[i]' represents the
+departure time of the i'th bus. you are also given a 0-indexed array
+'passengers' of length 'm' where 'passengers[j]' represents the arrival time
+of the j'th passenger. all bus departure times are unique. all passenger
+arrival times are unique. return the latest time you may arrive at the bus
+station to catch a bus. you cannot arrive at the same time as another
+passenger.
+"""
+
+
+class Solution(object):
+ def latestTimeCatchTheBus(self, buses, passengers, capacity):
+ """
+ :type buses: List[int]
+ :type passengers: List[int]
+ :type capacity: int
+ :rtype: int
+ """
+ buses.sort()
+ passengers.sort()
+ i, j = 0, 0
+ n, m = len(buses), len(passengers)
+ curr_cap = 0
+ while i < n:
+ curr_cap = 0
+ while j < m and curr_cap < capacity and passengers[j] <= buses[i]:
+ j += 1
+ curr_cap += 1
+ if i == n - 1:
+ j -= 1
+ if curr_cap < capacity:
+ time = buses[i]
+ while j >= 0 and time == passengers[j]:
+ time -= 1
+ j -= 1
+ return time
+ else:
+ time = passengers[j] - 1
+ j -= 1
+ while j <= 0 and time == passengers[j]:
+ time -= 1
+ j -= 1
+ return time
+ i += 1
+ return buses[-1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.latestTimeCatchTheBus(
+ buses=[10, 20], passengers=[2, 17, 18, 19], capacity=2
+ )
+ )
+ print(
+ obj.latestTimeCatchTheBus(
+ buses=[20, 30, 10], passengers=[19, 13, 26, 4, 25, 11, 21], capacity=2
+ )
+ )