# uber电面 新鲜面经

Find longest poolChain

input: List<Log>
output: 最长的poolchain

log结构:
Long timestamp
int driver_id
int passenger_id
String pickup / dropoff

poolchain的定义：

``````class Log:
def __init__(self, ts, di, pi, pd):
self.timestamp = ts
self.driverId = di
self.passengerId = pi
self.pickupOrDropoff = pd

class Trip:
def __init__(self, sl, el):
self.startLog = sl
self.endLog = el

class Solution:
def isOverlap(self, t1, t2):
if t1.startLog.timestamp > t2.endLog.timestamp or \
t2.startLog.timestamp > t1.endLog.timestamp:
return False
else:
return True
def findLongestPoolchain(self, logs):
from collections import defaultdict
trips = []
startTab = defaultdict(Log)
if log.pickupOrDropoff == "P":
startTab[log.driverId] = log
elif log.pickupOrDropoff == "D":
trip = Trip(startTab[log.driverId], log)
trips.append(trip)
del startTab[log.driverId]

trips.sort(key = lambda x: x.startLog.timestamp)
longestChain = 0
i = 0
j = 1
n = len(trips)
while i < n and j < n:
overlap = trips[i]
while j < n and self.isOverlap(overlap, trips[j]):
overlap.endLog.timestamp = max(overlap.endLog.timestamp, trips[j].endLog.timestamp)
j += 1
if j - i > longestChain:
longestChain = j - i
i = j
j += 1

return longestChain

### Test:
logs = [Log(101, 1, 1, "P"), Log(102, 1, 1, "D"), Log(105, 3, 3, "P"),
Log(107, 2, 2, "P"), Log(109, 2, 2, "D"),  Log(111, 3, 3, "D"),
Log(115, 1, 1, "P"), Log(120, 1, 1, "D")]

print(Solution().findLongestPoolchain(logs))
2

``````

dr1 -> p1 p2 d2 d1 p3 d3 --> chain: 2, 1
dr2 -> p1 p2 d2 p3 d1 d3 p4 d4 --> chain: 3, 1
output: 3

Anyway，以下是我的理解，说得不对还望指正！

1.对于每个driver而言，有一系列的trip，我们可以看作interval
2.然后我们对其按照starttime排序。求出overlap最多的trip个数。
3.最后对所以driver的max chain再得出一个全局的longest pool chain

ok的 我面试的时候也是按照driver id 存hashmap 再排序，然后不用set，直接用个counter就行了，来一个乘客，counter++,下一个，counter-- ; 这期间记录一下总共上了几个乘客，当counter =0的时候，update一下最大的乘客数