[LeetCode] 1094. Car Pooling

https://leetcode.com/problems/car-pooling/

Car Pooling - LeetCode

Car Pooling - Medium

 

capacity 만큼 좌석이 있는 차가 있다. trip 정보가 담긴 trips 벡터가 주어지는데,

trip의 정보는 각각 승객수, 타는 곳, 내리는 곳이다.

이 때, trips에 있는 모든 승객이 정원에 초과되지 않고 차에 타고 내릴 수 있는지 구하는 문제다.

 

trip이 (승객수, 타는 곳, 내리는 곳) 인데,

 

(타는 곳, 0, 승객 수)

(내리는 곳, 1, 승객 수)

 

와 같이 tuple을 만들자.

 

그리고 이 tuple을 타는곳/내리는곳의 번호에 따라 오름차순으로 priority queue pq에 저장한 후,

pq에서 하나씩 뽑아 타는 곳이었다면 승객 수에 +, 내리는 곳이었다면 승객 수에- 를 해주며

각각의 경우에 capacity를 초과하는지 살펴주면 된다.

주의할 점은 내리는 승객이 먼저라는 점이다.

 

전체 풀이 코드

class Solution {
public:
    struct compare {bool operator()(tuple<int,int,int> a, tuple<int,int,int> b) {return get<0>(a)==get<0>(b)?get<1>(a)<get<1>(b):get<0>(a)>get<0>(b);}};
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, compare> pq;
        int n = 0;
        for (auto trip:trips) {
            tuple<int, int, int> t = make_tuple(trip[1],0,trip[0]);
            pq.push(t);
            t = make_tuple(trip[2],1,trip[0]);
            pq.push(t);
        }
        while(!pq.empty()) {
            tuple<int, int, int> t = pq.top();
            pq.pop();
            n+=get<1>(t)==0?get<2>(t):-get<2>(t);
            if (n>capacity) return false;
        }
        return true;
    }
};