[LeetCode] 1701. Average Waiting Time

https://leetcode.com/problems/average-waiting-time/description/

leetcode - Average Waiting Time

문제 유형: 배열, 구현

문제 난이도 : Medium

 

문제

There is a restaurant with a single chef. You are given an array customers, where customers[i] = [arrivali, timei]:

• arrivali is the arrival time of the ith customer. The arrival times are sorted in non-decreasing order.
• timei is the time needed to prepare the order of the ith customer.

When a customer arrives, he gives the chef his order, and the chef starts preparing it once he is idle. The customer waits till the chef finishes preparing his order. The chef does not prepare food for more than one customer at a time. The chef prepares food for customers in the order they were given in the input.

Return the average waiting time of all customers. Solutions within 10-5 from the actual answer are considered accepted.

 

요리사가 한 명인 식당이 있다.

배열 customers를 받는다. customers[i] = [arrival_i, time_i]이다.

arrival_i는 i번째손님의 도착시간, time_i는 i번째 손님의 주문을 처리하는데 걸리는 시간이다.

 

손님이 오면, 주문을 넣는다. 요리사는 그의 일이 없을 때 요리를 시작한다.

손님은 그의 주문한 요리가 나올때까지 기다린다.

 

요리사는 한 번에 여러 음식을 할 수 없다.

한 명까지만 가능하다. 주문이 들어온 순서대로 요리를 처리한다.

 

모든 손님의 평균 대기시간을 구하시오.

10^-5까지의 부동소수점 오차를 허용합니다.

 

풀이

첫 손님은 추가 대기시간이 없다.

현재 시간에 대한 변수 currTime, 대기시간의 합 sum을 각각 customers[0][0] + customers[0][1]. customers[0][1]로 초기화한다.

그 뒤, 1번째 손님부터는..

 

이번 손님이 기다리는 시간은 기본 기다리는 시간인 customers[i][1]에다가, 추가 대기 시간이 존재할 경우, currTime - customers[i][0], 즉 현재 시간과 입장 시간의 차가 양수인 경우 더한다.

이번 손님처리가 끝나고 나서의 시간 currTime은 max(currTime, customers[i][0]) + customers[i][1]로 초기화한다.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers) {
        int n = customers.size();
        int currTime = customers[0][1] + customers[0][0];
        long long sum = customers[0][1];
        for(int i = 1; i < n; i++) {
            sum += customers[i][1] + (currTime > customers[i][0]? currTime - customers[i][0] : 0);
            currTime = max(currTime, customers[i][0]) + customers[i][1];
        }

        return (double)sum / n;
    }
};