Max Amount by Selling K Tickets

Problem Overview

Each row’s ticket price equals how many seats are still vacant in that row.

Intuition

Each row’s ticket price equals how many seats are still vacant in that row. To maximize revenue over k sales, always sell from the currently fullest row, then that row’s vacancy (and next price) drops by one. A max-heap keeps the richest row on top in O(log n) per sale.

Algorithm

1Push every arr[i] (vacant seats per row) into a max-heap.
2Repeat k times while the heap is non-empty: poll the largest value x, add x to the answer (mod 10^9+7).
3If x − 1 > 0, push x − 1 back (one seat sold from that row).
4Return the accumulated profit as an int.

Example Walkthrough

Input: arr = [2, 3], k = 3

1. Heap starts as {3, 2}.
2. Sale 1: take 3 → ans = 3; push 2 → heap {2, 2}.
3. Sale 2: take 2 → ans = 5; push 1 → heap {2, 1}.
4. Sale 3: take 2 → ans = 7; push 1 → heap {1, 1}.

Output: 7

Common Pitfalls

• Use a max-heap (reverseOrder), not a min-heap.
• Do not push 0 back — empty rows contribute nothing further.
• Accumulate in long and mod 1e9+7; k sales can overflow int mid-way.
• Stopping when the heap is empty handles selling more tickets than total seats.

Max Amount by Selling K Tickets.java

Java

// Approach: Max-heap of seat counts — each sale takes the row with the most vacant seats
// (price = vacancies), then push vacancies−1 back. Repeat k times; sum mod 1e9+7.
// Time: O((n + k) log n) Space: O(n)

import java.util.*;

class Solution {

    public int maxAmount(int[] arr, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());

        for (int i : arr) {
            q.add(i);
        }
        int mod = 1000000007;
        long ans = 0;
        while (!q.isEmpty() && k != 0) {
            int temp = q.poll();
            ans = (ans + temp) % mod;

            if (temp - 1 > 0) {
                q.add(temp - 1);
            }
            k--;

        }

        return (int) ans;
    }
}

Was this solution helpful?