forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy paththe-latest-time-to-catch-a-bus.py
More file actions
26 lines (25 loc) · 942 Bytes
/
Copy paththe-latest-time-to-catch-a-bus.py
File metadata and controls
26 lines (25 loc) · 942 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Time: O(nlogn + mlogm)
# Space: O(1)
# sort, two pointers
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()
cnt = j = 0
for i in xrange(len(buses)-1):
while j < len(passengers) and passengers[j] <= buses[i]:
cnt += 1
j += 1
cnt = max(cnt-capacity, 0)
j -= max(cnt-capacity, 0)
cnt = min(cnt, capacity)
while j < len(passengers) and passengers[j] <= buses[-1] and cnt+1 <= capacity:
cnt += 1
j += 1
return buses[-1] if cnt < capacity and (j-1 < 0 or passengers[j-1] != buses[-1]) else next(passengers[i]-1 for i in reversed(xrange(j)) if i-1 < 0 or passengers[i]-1 != passengers[i-1])