O(N*logN) time, O(N) space. Priority Queue
The problem is similar to the Job Scheduling.\nWhen we have rides sorted by start we can iterate them from left to right and build chains of rides. For each rid
The problem is similar to the [Job Scheduling](https://leetcode.com/problems/maximum-profit-in-job-scheduling/).\nWhen we have `rides` sorted by `start` we can iterate them from left to right and build **chains** of rides. For each ride:\n* check if there are rides which were finished before current (they are in the MinPriorityQueue sorted by end time)\n\t* if there are rides which were already finished it means that it\'s safe to take them before current ride and there is no sense skipping them. we take the ride with the maximum earnings.\n* add current ride earnings to the priority queue, we need to keep track of its `end` and how much `earnings` we can get from that chain (the best chain earnings before current ride is `maxEarnings` + earnings from curent ride)\n\nNow let\'s calculate Time and Space complexity. We sort `O(N logN)` and then iterate `N` times with adding/removing items from PriorityQueue which takes `O(logN)`. Space for sorting depends on the language (avg. `O(logN)`), and our PriorityQueue can have all rides in the worst case when they all overlap.\nTime: `O(N*logN)`\nSpace: `O(N)`\n\n```javascript\nvar maxTaxiEarnings = function(n, rides) {\n    rides.sort(([startA], [startB]) => startA - startB);\n    const pq = new MinPriorityQueue({priority: ([end]) => end});\n    let maxEarnings = 0;\n    \n    for (const [start, end, tip] of rides) {\n        while (!pq.isEmpty() && start >= pq.front().element[0]) {\n            const [_, earnings] = pq.dequeue().element;\n            maxEarnings = Math.max(maxEarnings, earnings);\n        }\n        pq.enqueue([end, maxEarnings + end - start + tip]);\n    }\n    \n    while (!pq.isEmpty()) {\n        const [_, earnings] = pq.dequeue().element;\n        maxEarnings = Math.max(maxEarnings, earnings);\n    }\n    \n    return maxEarnings;\n};\n```
['Heap (Priority Queue)', 'JavaScript']