# 1094. Car Pooling
###### tags: `Leetcode` `Medium` `Line Sweep`
Link: https://leetcode.com/problems/car-pooling/
## 思路 $O(max(N, 1001))$ $O(1001)$ N是trips的长度
和[0253. Meeting Rooms II](https://hackmd.io/-UTPnVO1SWqRc8em20pV0g) 有点像的一道题 也可以用它的方法解，但是因为这次给的input已经是排好序的了，所以时间复杂度不需要到O(NlogN)

**差分法**
开一个array 横轴为时间
对于每一个上车或者下车的时间，记录上车或下车的人数
之后再用culumative sum，就能算出每个时间在车上的人数，如果大于capacity则return false
## Code

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] cnt = new int[1001];
        for(int i = 0;i < trips.length;i++){
            cnt[trips[i][1]] += trips[i][0];
            cnt[trips[i][2]] -= trips[i][0];
        }
        
        int total = 0;
        for(int num:cnt){
            total += num;
            if(total > capacity){
                return false;
            }
        }
        return true;
   }
}