Problem statement

https://binarysearch.com/problems/Uber-Pool/

Solution

Sort events and then use line sweep to count how many we have in each moment of time.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, trips, capacity):
        points = [(x, z) for x, y, z in trips]
        points += [(y, -z) for x, y, z in trips]
        total = 0
        for x, gain in sorted(points):
            total += gain
            if total > capacity: return False

        return True