https://leetcode.com/problems/car-pooling

Let us start with example and understand what exactly we are asked to do: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11. Let us represent it in the following way:

# # 3 3 3 3 3 # # # # # # # # # # 3 3 3 # # # 8 8 8 8 8 8 8

Now, the question is we sum all these lists, where we deal # as 0 (0 0 3 11 11 11 11 11 11 11) will some number be more than capacity = 11 or not. Let us instead each list construct another list, such that its cumulative sum is our list:

0 0 3 0 0 0 0 -3 0 0 0 0 0 0 0 0 0 0 3 0 0 -3 0 0 0 8 0 0 0 0 0 0 -8

Then if we sum these lists and evaluate cumulative sums, we will have exactly what is needed:

0 0 3 8 0 0 0 0 0 0 -11 -> cumulative sums -> 0 0 3 11 11 11 11 11 11 11 0

Complexity: time and space complexity is O(m), where m is maximum point of time we have.

class Solution:
    def carPooling(self, trips, capacity):
        m = max([i for _,_,i in trips])
        times = [0]*(m+2)
        for i,j,k in trips:
            times[j+1] += i
            times[k+1] -= i
        return max(accumulate(times)) <= capacity

If you like the solution, you can upvote it on leetcode discussion section: Problem 1094