Vultr DocsLatest Content

Time Needed to Buy Tickets

Updated on 14 July, 2025
Time Needed to Buy Tickets header image

Problem Statement

In this scenario, we are tasked with simulating people lined up to buy tickets, where each person buys a ticket one at a time. You are provided with a 0-indexed array tickets, where tickets[i] specifies the total number of tickets the i-th person wants to purchase. A crucial element of the simulation is that it takes exactly one second for a person to buy a single ticket. After purchasing, the person must rejoin the end of the line to buy another, unless they have no more tickets to purchase, in which case they leave the line. The goal is to calculate the total time required for the person at position k to purchase all their desired tickets and leave the queue.

Examples

Example 1

Input:

tickets = [2,3,2], k = 2

Output:

6

Explanation:

* The queue starts as [2,3,2], where the kth person is underlined.
* After the person at the front has bought a ticket, the queue becomes [3,2,1] at 1 second.
* Continuing this process, the queue becomes [2,1,2] at 2 seconds.
* Continuing this process, the queue becomes [1,2,1] at 3 seconds.
* Continuing this process, the queue becomes [2,1] at 4 seconds. Note: the person at the front left the queue.
* Continuing this process, the queue becomes [1,1] at 5 seconds.
* Continuing this process, the queue becomes [1] at 6 seconds. The kth person has bought all their tickets, so return 6.

Example 2

Input:

tickets = [5,1,1,1], k = 0

Output:

8

Explanation:

* The queue starts as [5,1,1,1], where the kth person is underlined.
* After the person at the front has bought a ticket, the queue becomes [1,1,1,4] at 1 second.
* Continuing this process for 3 seconds, the queue becomes [4] at 4 seconds.
* Continuing this process for 4 seconds, the queue becomes [] at 8 seconds. The kth person has bought all their tickets, so return 8.

Constraints

  • n == tickets.length
  • 1 <= n <= 100
  • 1 <= tickets[i] <= 100
  • 0 <= k < n

Approach and Intuition

The process can be approached by iteratively reducing the ticket numbers in the tickets array until the person at position k has bought all their tickets. Here's a step-by-step approach:

  1. Start by initializing time to 0. This will count the total seconds passed.
  2. Use a loop to iterate through the ticket buying process.
    • For every person in the queue, check if they still need to buy tickets (tickets[i] > 0). If they do, reduce tickets[i] by 1 and increment the time by 1.
    • Check if i is equal to k (i.e., we are processing the person at position k). If tickets[k] is reduced to 0 during this iteration, the person at position k has bought all their tickets, and you can break out of the loop and return the time.
  3. After processing one round (i.e., a single interaction for all persons in the queue):
    • If it's not yet the turn of the person at k or if they still have tickets left, continue the loop.

Using the provided examples:

  • Example 1: With tickets = [2,3,2] and k = 2, we calculate by iteratively processing each person:

    • The queue decreases sequentially in rounds, starting from every person buying one ticket from the front to the end, then moving back to the front.
    • It takes 6 seconds for the third person to buy all their tickets, as depicted in the example outline with everyone else's number also reducing incrementally.

  • Example 2: With tickets = [5,1,1,1] and k = 0, where the front person needs the maximum tickets:

    • As others have lesser tickets, they leave the queue sooner.
    • It takes 8 seconds for the first person to finish buying given the occasional returns to the back of the queue after each ticket purchase.

This approach provides a straightforward simulation of the ticket buying process using simple iteration and conditional checks, effectively calculating the required outcome with each person's actions impacting the overall state of the queue.

Solutions

  • C++
cpp 
class Solution {
public:
    int calculateTimeToBuyTickets(vector<int>& ticketList, int kPosition) {
        int totalTime = 0;
            
        for (int j = 0; j < ticketList.size(); j++) {
            if (j <= kPosition) {
                totalTime += min(ticketList[kPosition], ticketList[j]);
            } else {
                totalTime += min(ticketList[kPosition] - 1, ticketList[j]);
            }
        }
            
        return totalTime;
    }
};

The given C++ solution addresses the problem of calculating the required time to buy tickets. The function calculateTimeToBuyTickets receives two parameters:

  • ticketList: a vector of integers representing the number of tickets each person in the queue intends to buy.
  • kPosition: an integer indicating the position of a specific person in the queue (zero-indexed).

The function calculates the total time needed for the person at position kPosition to buy their tickets. The process for determining the time is as follows:

  1. Intialize totalTime to zero, which accumulates the total amount of time taken.
  2. Iterate through each person in the queue using a for loop.
    • If the current person’s position (j) is less than or equal to kPosition, add the minimum of the ticket numbers of the person at kPosition or the person at position j to totalTime.
    • If the current position is greater than kPosition, add the minimum of ticketList[kPosition] - 1 or ticketList[j] to totalTime. This accounts for the fact that the person at kPosition would have already bought one of their tickets by the time people beyond kPosition start buying.

The function finally returns the totalTime after the loop completes.

This solution efficiently calculates the total time by comparing each person's tickets to purchase with the tickets required by the person at kPosition, ensuring all possibilities are covered through conditional checking within the loop. Consider the handling of edge cases, such as when all individuals have the same number of tickets or the minimal variation in the ticket counts, for better performance and accuracy.

  • Java
java 
class Solution {
    public int calculateTime(int[] queueTickets, int target) {
        int totalTime = 0;
            
        for (int index = 0; index < queueTickets.length; index++) {
            // Process based on position relative to target
            if (index <= target) {
                totalTime += Math.min(queueTickets[target], queueTickets[index]);
            } else {
                totalTime += Math.min(queueTickets[target] - 1, queueTickets[index]);
            }
        }
            
        return totalTime;
    }
}

The method calculateTime calculates the total time required to buy tickets from a queue, considering the number of tickets each person wants to buy (queueTickets) and the position of the person of interest (target). Below is a step-by-step explanation of how the method works:

  • Initialize totalTime to zero to keep track of the accumulated time.

  • Iterate through each person in the queue using a for loop, where index represents the current person's position.

  • If the current person's position (index) is before or at the target position:

    • Add the minimum of the tickets required by the person at target and the current person to totalTime.

  • If the current person's position (index) is after the target:

    • Add the minimum value between one less than the tickets required by the person at target and the current person's requirement to totalTime.

  • After the loop completes, return the totalTime which now contains the total time taken for the target person to buy their tickets.

This approach ensures that the function efficiently calculates the required time based on the number of tickets each person in the queue needs and their relative position to the target buyer.

  • Python
python 
class Solution:
    def timeToPurchase(self, tickets: List[int], k: int) -> int:
        time_spent = 0
            
        for idx in range(len(tickets)):
            if idx <= k:
                time_spent += min(tickets[k], tickets[idx])
            else:
                time_spent += min(tickets[k] - 1, tickets[idx])
            
        return time_spent

This Python solution efficiently calculates the time needed to buy tickets in a queue. Implementing the timeToPurchase method in the Solution class, the code takes two parameters: tickets, a list indicating the number of tickets each person needs to buy, and k, the index of the person whose total time to finish buying tickets is to be calculated.

Here is how the solution works:

  • Initialize time_spent to zero, which will accumulate the total time spent.
  • Iterate through each person indexed by idx in the queue (tickets list) using a for loop.
  • For each person before or including k, add the smaller of the number of tickets k needs or the current person needs (tickets[k] or tickets[idx]) to time_spent.
  • For each person after k, add the smaller number of tickets considering tickets[k] - 1 or tickets[idx]. This -1 accounts for the fact that after k buys all their tickets, everyone else would have had one less turn to buy.
  • Return the accumulated time_spent, which gives the total minutes needed for the k-th person to purchase all their tickets.

This approach ensures that the function calculates the exact time taken based on the queued positions and efficiently covers scenarios where not all people need the same number of tickets.

Comments

No comments yet.