Car Pooling(Array,Sorting,Heap (Priority Queue),Simulation,Prefix Sum)

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

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

 

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

 

Constraints:

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengersi <= 100
• 0 <= fromi < toi <= 1000
• 1 <= capacity <= 105

좀 짜친다. 뭔가 list를 sorting하고 싶은데, list의 중간 element 기준으로 sorting하면 room reservation 문제처럼 풀 수 있을 거 같지만, 그 sorting을 어떻게 해야할지가 애매허네

 

어렵다.. Naive하게도 잘 풀리지 않는다. 뭔가 Solution은 그렇게 어려울 거 같지 않은데 왜 안 풀릴까 ㅠ

 

 

1. Python

겁나 추찹하게 일단 풀긴 풀었다. 안도의 한숨 ㅋㅋ.. 뭔가 효율은 굉장히 좋지 않아보이는데,, 뭐 어떠한가

일단 풀리는게 어디고 ㅠ

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        lst = [0]*1000
        for x in trips:
            for i in range(x[1],x[2]):
                lst[i] += x[0]
            if max(lst) > capacity : return False  
        return True

비슷한 방법인데 아래처럼 하니까

시간 효율이 확 산다.

 

역시 for문을 겹치냐 안 겹치냐의 차이로 속도차이가 확 나는구만

 

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # 타임라인 배열 생성 (최대 위치 1000)
        timeline = [0] * 1001
        
        # 승객 변화량 기록
        for passengers, start, end in trips:
            timeline[start] += passengers  # 시작 위치에서 승객 추가
            timeline[end] -= passengers    # 종료 위치에서 승객 제거
        
        # Prefix Sum 계산하여 최대 용량 확인
        current_capacity = 0
        for passengers in timeline:
            current_capacity += passengers
            if current_capacity > capacity:
                return False
        
        return True

 

heap 방법도 solution을 보았는데, 뭔 소린지 모르겄다.

 

일단 코드는 아래와 같은데, 위 방법보다 더 복잡해보인다.

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // 시작 시간 기준으로 trips 정렬
        sort(trips.begin(), trips.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1]; // 시작 시간 기준 정렬
        });

        // 최소 힙 (종료 시간 기준)
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;

        int currentCapacity = 0;

        for (const auto& trip : trips) {
            int passengers = trip[0];
            int start = trip[1];
            int end = trip[2];

            // 현재 시점 이전에 내릴 승객 처리
            while (!minHeap.empty() && minHeap.top().first <= start) {
                currentCapacity -= minHeap.top().second;
                minHeap.pop();
            }

            // 새로운 승객 태우기
            minHeap.emplace(end, passengers);
            currentCapacity += passengers;

            // 용량 초과 확인
            if (currentCapacity > capacity) {
                return false;
            }
        }

        return true;
    }
};