Daily Question – 2073. Time Needed to Buy Tickets

Description: https://leetcode.com/problems/time-needed-to-buy-tickets/description/

Code: Time complexity O(n2)

public static int timeRequiredToBuy(int[] tickets, int k) {
        int count = 0;
        while (tickets[k] > 0) {
            for (int i=0;i<tickets.length;i++) if (tickets[i] > 0) {
                tickets[i]--;
                count++;
                if (tickets[k] == 0) return count;
            }
        }
        return count;
    }

Can be simplified to O(n) as we do not need to iterate every time to count the time.

public static int timeRequiredToBuy(int[] tickets, int k) {
    int time = 0;
    for (int i = 0; i < tickets.length; i++) {
        if (i <= k) {
            // 对于索引k及之前的人，我们取他们的票数与k的票数的较小值
            time += Math.min(tickets[i], tickets[k]);
        } else {
            // 对于索引k之后的人，我们只需要考虑在k之前他们能买的票数
            time += Math.min(tickets[i], tickets[k] - 1);
        }
    }
    return time;
}