Approach

Use a max heap to keep track of the largest number of tickets among all windows.
- Use a max heap to efficiently extract the maximum value and re-insert reduced values.
Steps to solve:
- Insert all initial ticket counts into a max heap.
- For k iterations:
  - Extract the maximum from the heap (largest ticket window).
  - Deduct one ticket from the count of that window and add its previous value to the revenue.
  - Re-insert the reduced count back into the heap.
Return the total revenue after k iterations.

Code

[{"language":"C++","code":"#include <iostream>\n#include <vector>\n#include <queue>\nusing namespace std;\n\nclass Solution {\npublic:\n    int maxRevenue(int N, int k, vector<int>& tickets) {\n        priority_queue<int> maxHeap(tickets.begin(), tickets.end());\n        int revenue = 0;\n\n        for (int i = 0; i < k; i++) {\n            int maxTickets = maxHeap.top();\n            maxHeap.pop();\n            revenue += maxTickets;\n            maxHeap.push(maxTickets - 1);\n        }\n        return revenue;\n    }\n};\n\nint main() {\n    Solution solution;\n    vector<int> tickets = {5, 1, 7, 10, 11, 9};\n    int N = 6, k = 4;\n    cout << solution.maxRevenue(N, k, tickets) << endl; // Output: 40\n    return 0;\n}","lang":"cpp"},{"language":"Go","code":"package main\n\nimport (\n\t\"container/heap\"\n\t\"fmt\"\n)\n\ntype MaxHeap []int\n\nfunc (h MaxHeap) Len() int           { return len(h) }\nfunc (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }\nfunc (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }\n\nfunc (h *MaxHeap) Push(x any) {\n\t*h = append(*h, x.(int))\n}\n\nfunc (h *MaxHeap) Pop() any {\n\told := *h\n\tx := old[len(old)-1]\n\t*h = old[:len(old)-1]\n\treturn x\n}\n\nfunc maxRevenue(N, k int, tickets []int) int {\n\th := MaxHeap(tickets)\n\theap.Init(&h)\n\n\trevenue := 0\n\tfor i := 0; i < k; i++ {\n\t\tmaxTickets := heap.Pop(&h).(int)\n\t\trevenue += maxTickets\n\t\theap.Push(&h, maxTickets-1)\n\t}\n\treturn revenue\n}\n\nfunc main() {\n\ttickets := []int{5, 1, 7, 10, 11, 9}\n\tN, k := 6, 4\n\tfmt.Println(maxRevenue(N, k, tickets)) // Output: 40\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int maxRevenue(int N, int k, int[] tickets) {\n        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);\n\n        for (int ticket : tickets) {\n            maxHeap.offer(ticket);\n        }\n\n        int revenue = 0;\n        for (int i = 0; i < k; i++) {\n            int maxTickets = maxHeap.poll();\n            revenue += maxTickets;\n            maxHeap.offer(maxTickets - 1);\n        }\n\n        return revenue;\n    }\n\n    public static void main(String[] args) {\n        Solution solution = new Solution();\n        int[] tickets = {5, 1, 7, 10, 11, 9};\n        int N = 6, k = 4;\n        System.out.println(solution.maxRevenue(N, k, tickets)); // Output: 40\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun maxRevenue(N: Int, k: Int, tickets: IntArray): Int {\n        val maxHeap = PriorityQueue<Int>(compareByDescending { it })\n        tickets.forEach { maxHeap.add(it) }\n\n        var revenue = 0\n        repeat(k) {\n            val maxTickets = maxHeap.poll()\n            revenue += maxTickets\n            maxHeap.add(maxTickets - 1)\n        }\n\n        return revenue\n    }\n}\n\nfun main() {\n    val tickets = intArrayOf(5, 1, 7, 10, 11, 9)\n    val N = 6\n    val k = 4\n    val solution = Solution()\n    println(solution.maxRevenue(N, k, tickets)) // Output: 40\n}","lang":"kotlin"},{"language":"Python","code":"import heapq\n\nclass Solution:\n    def maxRevenue(self, N, k, tickets):\n        max_heap = [-t for t in tickets]\n        heapq.heapify(max_heap)\n\n

Related Tags

Continue Practicing