2073. Time Needed to Buy Tickets

Задача

Дана очередь tickets (сколько билетов покупает каждый) и позиция k. Верните время, за которое человек на позиции k купит все билеты.

Решение

Решение

/**
 * Временная сложность: O(n)
 * Пространственная сложность: O(1)
 */
var timeRequiredToBuy = function(tickets, k) {
    let time = 0;
    const targetTickets = tickets[k];
 
    for (let i = 0; i < tickets.length; i++) {
        if (i <= k) {
            // Люди до k-го человека (включительно) могут купить максимум targetTickets билетов
            time += Math.min(tickets[i], targetTickets);
        } else {
            // Люди после k-го человека могут купить максимум (targetTickets - 1) билетов
            time += Math.min(tickets[i], targetTickets - 1);
        }
    }
 
    return time;
};

Решение 2

/**
 * Time: O(n × m) (симуляция по секундам), Space: O(1)
 */
var timeRequiredToBuy = function(tickets, k) {
    let remainingTickets = tickets[k];
    let seconds = 0;
    let position = 0;
 
    while (remainingTickets) {
        if (position >= tickets.length) position = 0;
 
        if (tickets[position] == null) {
            position++;
            continue;
        }
 
        tickets[position]--;
        seconds++;
 
        if (position === k) remainingTickets--;
 
        if (tickets[position] === 0) tickets[position] = null;
 
        position++;
    }
 
    return seconds;
};