Java | PriorityQueue | O(NlogN) time | O(N) space | Easy solution same as max profit in job schedule
Approach\n Describe your first thoughts on how to solve this problem. \nIntuition behind this is same as maximum profit in job scheduling problem.\n1. Sort ride
# Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\nIntuition behind this is same as maximum profit in job scheduling problem.\n1. Sort rides based on start time.\n2. Use min heap(priority queue) while comparing end time.\n3. Keep adding to the queue with cumulative profit. \n4. Keep track of max profit.\n\nNote : Used Long array in queue instead of int array, since max value can be long and if int array was used, some of the test cases fail.\n\n# Complexity\n- Time complexity:O(NlogN)\n Sorting ride take O(NlogN). Iterating through each ride would take O(N). Hence total is (N + NlogN) = O(NlogN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n  \n\n- Space complexity: O(N). We store each ride in the queue ammounting to worst case O(N) time.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public long maxTaxiEarnings(int n, int[][] rides) {\n        //Sort based on start time\n        Arrays.sort(rides, (a,b) -> a[0] - b[0]);\n        long max = 0;\n\n        //Storing Long array instead of Int array, since max value is long.\n        //Sort based on end time\n        PriorityQueue<long[]> myQueue = new PriorityQueue<long[]>((a,b) -> Long.compare(a[0],b[0]));\n\n        for (int i = 0; i < rides.length; i++) {\n            int start = rides[i][0];\n            int end = rides[i][1];\n            long profit = end - start + Long.valueOf(rides[i][2]);\n\n            while (!myQueue.isEmpty() && start >= myQueue.peek()[0]) {\n                max = Math.max(max, myQueue.peek()[1]);\n                myQueue.poll();\n            }\n            myQueue.offer(new long[] {end, profit + max});\n        }\n\n        while (!myQueue.isEmpty()) {\n            max = Math.max(max, myQueue.poll()[1]);\n        }\n\n        return max;\n    }\n}\n\n```
['Heap (Priority Queue)', 'Java']