Maximize the profit after selling the tickets

Problem Link

Maximize the Profit after Selling the Tickets – GeeksforGeeks

Problem: Maximize the Profit after Selling the Tickets

Problem Statement

There are N ticket counters and each counter has a certain number of tickets. You have to sell k tickets such that each time you sell a ticket from a counter, you earn the number of tickets currently remaining at that counter as profit, and then the number of tickets at that counter reduces by 1.

Your task is to maximize the total profit from selling k tickets.

Examples

Example 1
Input: A = [5, 2, 1], k = 4
Output: 11
Explanation: Sell 1 ticket from counter with 5 → profit = 5
Sell from 4 → profit = 4
Sell from 2 → profit = 2
Sell from 1 → profit = 0 (since now 1 became 0)
Total = 5 + 4 + 2 + 0 = 11

Example 2
Input: A = [2, 3, 5, 4], k = 5
Output: 22
Explanation: Pick highest available ticket count repeatedly.

Constraints

• 1 <= N <= 10⁵

• 1 <= A[i] <= 10⁹

• 1 <= k <= 10⁹

Intuition

To maximize profit, we must always sell the ticket from the counter that currently has the highest number of tickets. This is a greedy problem that naturally leads to the use of a max-heap to always retrieve the maximum available ticket count in O(log N) time.

Approach

1. Use a max-heap (priority queue in descending order) to store the number of tickets at each counter.

2. Repeat the following for k times:

   • Remove the counter with the maximum number of tickets.

   • Add its current value to total profit.

   • Decrease its value by 1 and push it back if it’s still > 0.

3. Return the total profit after k iterations.

Code (Java)

import java.util.*;

class Solution {
    public long maxProfit(int[] A, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int val : A) {
            pq.add(val);
        }

        long profit = 0;
        while (k-- > 0 && !pq.isEmpty()) {
            int max = pq.poll();
            profit += max;
            if (max - 1 > 0) {
                pq.add(max - 1);
            }
        }

        return profit;
    }
}

Time and Space Complexity

• Time Complexity: O(k log N)
  Each extraction and reinsertion into the heap takes O(log N). This runs k times.

• Space Complexity: O(N)
  The heap stores up to N elements.

Dry Run

Input: A = [5, 2, 1], k = 4

• Initialize max-heap: [5, 2, 1]

• Iteration 1: Poll 5 → profit += 5 → push 4 → heap = [4, 1, 2]

• Iteration 2: Poll 4 → profit += 4 → push 3 → heap = [3, 1, 2]

• Iteration 3: Poll 3 → profit += 3 → push 2 → heap = [2, 1, 2]

• Iteration 4: Poll 2 → profit += 2 → push 1 → heap = [2, 1, 1]

Total profit = 5 + 4 + 3 + 2 = 14

Conclusion

This is a greedy problem that maximizes profit by always choosing the highest remaining ticket count. A max-heap provides the optimal structure for efficiently retrieving and updating the largest elements, ensuring optimal results in large datasets.