1 class Solution: 2 def carPooling(self, trips: ‘List[List[int]]‘, capacity: int) -> bool: 3 n = len(trips) 4 if n == 0: 5 return True 6 elif n == 1: 7 return True if trips[0][0] <= capacity else False 8 9 trips = sorted(trips,key=lambda x:[x[1],x[2]]) 10 #print(trips) 11 12 cursum = trips[0][0] 13 begin = trips[0][1] 14 end = trips[0][2] 15 l = [0] 16 for i in range(1,n): 17 if end > trips[i][1]: 18 cursum += trips[i][0] 19 begin = max(begin,trips[i][1]) 20 end = min(end,trips[i][2]) 21 l.append(i) 22 else: 23 begin = max(begin,trips[i][1]) 24 end = min(end,trips[i][2]) 25 j = 0 26 while len(l) > 0 and j < len(l): 27 pre = trips[l[j]] 28 if pre[2] <= begin: 29 cursum -= pre[0] 30 l.pop(j) 31 else: 32 j += 1 33 cursum += trips[i][0] 34 l.append(i) 35 minend = 1001 36 for k in range(len(l)): 37 if minend > trips[l[k]][2]: 38 minend = trips[l[k]][2] 39 end = minend 40 41 if cursum > capacity: 42 return False 43 return True
基本思路：计算有相交区域的乘客的数量和，如果超过容量则返回false。
这样的代码怎么看都不是最优的，执行时间也并不让人满意。
下面给出讨论区中高手的代码，无论是代码的可读性和执行效率都很好。
参考地址：https://leetcode.com/problems/car-pooling/discuss/317712/Simple-Python-solution-(Meeting-Rooms-II)
1 class Solution: 2 def carPooling(self, trips: ‘List[List[int]]‘, capacity: int) -> bool: 3 lst = [] 4 for n, start, end in trips: 5 lst.append((start, n)) 6 lst.append((end, -n)) 7 lst.sort() 8 pas = 0 9 for loc in lst: 10 pas += loc[1] 11 if pas > capacity: 12 return False 13 return True
总结一下吧，做1093题时，看了一个多小时才明白题意，做完那道题目，就有点迷糊了。
做这道题时，之前没有做过leetcode 253 Meeting Room II，所以没有已有的“模版”可以直接套用。
没有算法思想的支撑，不能把问题转化为简化的模型，就只从题意本身硬编码解决了。
能硬解出来，也行！
原文：https://www.cnblogs.com/asenyang/p/11072432.html