[leetcode #1094] Car Pooling

Problem

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 trip[i] = [numPassengersᵢ, fromᵢ, toᵢ] indicates that the ith trip has numPassengersᵢ passengers and the locations to pick them up and drop them off are fromᵢ and toᵢ 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 <= numPassengersᵢ <= 100
・ 0 <= fromᵢ < toᵢ <= 1000
・ 1 <= capacity <= 105

Idea

처음에는 pickup과 dropoff를 따로 관리하고 trips에서 타는 시간과 내리는 시간을 event로 간주해 정렬한 뒤 event 순으로 승객 수를 확인하면서 풀었는데 그럴 필요가 없었다.

우선 승객수를 관리할 배열을 만든다. trips의 최대 범위가 1000이므로 1001의 크기로 만들었다.

주어진 trips를 탐색하면서 승객들이 타는 시간에 승객수를 더하고 내리는 시간에 승객수를 뺀다.

승객수 배열을 탐색하면서 capacity에서 승객수를 빼고, capacity가 0보다 작다면 곧바로 false를 리턴한다.

배열의 탐색이 끝나면 모든 승객을 타고 내리게 할 수 있다는 뜻이므로 true를 리턴한다.

Solution

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] passengers = new int[1001];

        for (int[] trip : trips) {
            passengers[trip[1]] += trip[0];
            passengers[trip[2]] -= trip[0];
        }

        for (int i=0; i < passengers.length; i++) {
            capacity -= passengers[i];
            if (capacity < 0) {
                return false;
            }
        }

        return true;
    }
}

Reference

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