leetcode_practice/1094-car-pooling.cpp at main · ssarmin/leetcode_practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//https://leetcode.com/problems/car-pooling/
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        map<int, int> m;
        for(auto t: trips){
            m[t[1]] += t[0];
            m[t[2]] -= t[0];
            if(m[t[1]] > capacity)
                return false;
        }
        int count = 0;
        for(auto a: m){
            count += a.second;
            if(count > capacity)
                return false;
        }
        return true;
    }
};
/*
[[8, 16, 20], [9, 18, 19], [7, 13, 16], [7, 13, 16], [8, 15, 18], [3, 17, 18], [6, 6, 18], [1, 2, 6], [5, 3, 7], [1, 16, 20], [3, 12, 20], [8, 18, 20], [5, 7, 17], [9, 14, 15], [7, 9, 17], [7, 12, 18], [6, 15, 19], [6, 18, 19], [8, 18, 20], [2, 12, 16]]
58
[[8, 16, 20], [9, 18, 19], [7, 13, 16], [7, 13, 16], [8, 15, 18], [3, 17, 18], [6, 6, 18], [1, 2, 6], [5, 3, 7], [1, 16, 20], [3, 12, 20], [8, 18, 20], [5, 7, 17], [9, 14, 15], [7, 9, 17], [7, 12, 18], [6, 15, 19], [6, 18, 19], [8, 18, 20], [2, 12, 16]]
57
[[8, 16, 20], [9, 18, 19], [7, 13, 16], [7, 13, 16], [8, 15, 18], [3, 17, 18], [6, 6, 18], [1, 2, 6], [5, 3, 7], [1, 16, 20], [3, 12, 20], [8, 18, 20], [5, 7, 17], [9, 14, 15], [7, 9, 17], [7, 12, 18], [6, 15, 19], [6, 18, 19], [8, 18, 20], [2, 12, 16]]
59
[[7,5,6],[6,7,8],[10,1,6]]
16
[[9,3,4],[9,1,7],[4,2,4],[7,4,5]]
23
*/