Maximum revenue by selling K tickets from N windows

Problem

Given N windows where each window contains a specific number of tickets, the price of a ticket at a window is equal to the number of tickets remaining at that window. You need to sell k tickets in such a way that it generates the maximum revenue. The number of tickets at each window decreases as tickets are sold.

Examples

Example 1

Input:
N = 6, k = 4
Tickets = [5, 1, 7, 10, 11, 9]

Output:
40

Explanation:
- Sell the first ticket from window 5 (cost = 11). Revenue = 11.
- Sell the second ticket from window 4 or 5 (cost = 10). Revenue = 21.
- Sell the third ticket from window 4 (cost = 10). Revenue = 31.
- Sell the fourth ticket from window 4, 5, or 6 (cost = 9). Revenue = 40.

Solution

Method 1 - Using max heap

Reasoning/Intuition

To achieve maximum revenue:

1. Always sell a ticket from the window with the maximum number of tickets available, as its cost (revenue per ticket) will be highest.
2. This ensures that you are maximising revenue at each step.
3. After selling a ticket from a window, decrease its ticket count and adjust its contribution to subsequent decisions.

This can be efficiently handled using a priority queue/max heap, where the maximum number of tickets at any window is always at the top. At each step:

• Extract the window with the maximum tickets.
• Sell one ticket and reduce the ticket count. Push the updated value back into the heap.

Approach

1. 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.
2. 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.
3. Return the total revenue after k iterations.

Code

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int maxRevenue(int N, int k, vector<int>& tickets) {
        priority_queue<int> maxHeap(tickets.begin(), tickets.end());
        int revenue = 0;

        for (int i = 0; i < k; i++) {
            int maxTickets = maxHeap.top();
            maxHeap.pop();
            revenue += maxTickets;
            maxHeap.push(maxTickets - 1);
        }
        return revenue;
    }
};

int main() {
    Solution solution;
    vector<int> tickets = {5, 1, 7, 10, 11, 9};
    int N = 6, k = 4;
    cout << solution.maxRevenue(N, k, tickets) << endl; // Output: 40
    return 0;
}

Go

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func maxRevenue(N, k int, tickets []int) int {
	h := MaxHeap(tickets)
	heap.Init(&h)

	revenue := 0
	for i := 0; i < k; i++ {
		maxTickets := heap.Pop(&h).(int)
		revenue += maxTickets
		heap.Push(&h, maxTickets-1)
	}
	return revenue
}

func main() {
	tickets := []int{5, 1, 7, 10, 11, 9}
	N, k := 6, 4
	fmt.Println(maxRevenue(N, k, tickets)) // Output: 40
}

Java

class Solution {
    public int maxRevenue(int N, int k, int[] tickets) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        for (int ticket : tickets) {
            maxHeap.offer(ticket);
        }

        int revenue = 0;
        for (int i = 0; i < k; i++) {
            int maxTickets = maxHeap.poll();
            revenue += maxTickets;
            maxHeap.offer(maxTickets - 1);
        }

        return revenue;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] tickets = {5, 1, 7, 10, 11, 9};
        int N = 6, k = 4;
        System.out.println(solution.maxRevenue(N, k, tickets)); // Output: 40
    }
}

Kotlin

class Solution {
    fun maxRevenue(N: Int, k: Int, tickets: IntArray): Int {
        val maxHeap = PriorityQueue<Int>(compareByDescending { it })
        tickets.forEach { maxHeap.add(it) }

        var revenue = 0
        repeat(k) {
            val maxTickets = maxHeap.poll()
            revenue += maxTickets
            maxHeap.add(maxTickets - 1)
        }

        return revenue
    }
}

fun main() {
    val tickets = intArrayOf(5, 1, 7, 10, 11, 9)
    val N = 6
    val k = 4
    val solution = Solution()
    println(solution.maxRevenue(N, k, tickets)) // Output: 40
}

Python

import heapq

class Solution:
    def maxRevenue(self, N, k, tickets):
        max_heap = [-t for t in tickets]
        heapq.heapify(max_heap)

        revenue = 0
        for _ in range(k):
            max_tickets = -heapq.heappop(max_heap)
            revenue += max_tickets
            heapq.heappush(max_heap, -(max_tickets - 1))

        return revenue

# Testing
tickets = [5, 1, 7, 10, 11, 9]
N, k = 6, 4
solution = Solution()
print(solution.maxRevenue(N, k, tickets)) # Output: 40

Rust

struct Solution;

impl Solution {
    pub fn max_revenue(n: usize, k: i32, tickets: Vec<i32>) -> i32 {
        let mut max_heap = BinaryHeap::from(tickets);
        let mut revenue = 0;

        for _ in 0..k {
            if let Some(max_tickets) = max_heap.pop() {
                revenue += max_tickets;
                max_heap.push(max_tickets - 1);
            }
        }
        revenue
    }
}

fn main() {
    let tickets = vec![5, 1, 7, 10, 11, 9];
    let n = 6;
    let k = 4;
    println!("{}", Solution::max_revenue(n, k, tickets)); // Output: 40
}

Complexity

• ⏰ Time complexity: O(N + k * log N)
  • Heap creation: O(N).
  • For each of the k tickets, heap extract and insert operations take O(log N).
  • Total: O(N + k * log N).
• 🧺 Space complexity: O(N), to store the heap.