LeetCode-1094 拼车

题目连接：数组

源自LeetCode第142场周赛spa

https://leetcode-cn.com/contest/weekly-contest-142/problems/car-pooling/code

题目描述：排序

假设你是一位顺风车司机，车上最初有 capacity 个空座位能够用来载客。因为道路的限制，车 只能 向一个方向行驶（也就是说，不容许掉头或改变方向，你能够将其想象为一个向量）。ip

这儿有一份行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了你的第 i 次行程信息：ci

• 必须接送的乘客数量；
• 乘客的上车地点；
• 以及乘客的下车地点。

这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们必定在你的行驶方向上）。leetcode

请你根据给出的行程计划表和车子的座位数，来判断你的车是否能够顺利完成接送所用乘客的任务（当且仅当你能够在全部给定的行程中接送全部乘客时，返回 true，不然请返回 false）。get

示例 1：it

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：io

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

示例 3：

输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true

示例 4：

输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true

提示：

1. 你能够假设乘客会自觉遵照 “先下后上” 的良好素质
2. trips.length <= 1000
3. trips[i].length == 3
4. 1 <= trips[i][0] <= 100
5. 0 <= trips[i][1] < trips[i][2] <= 1000
6. 1 <= capacity <= 100000

题目大意：

汽车只能单向行驶，沿途能够上下客，汽车有容量，给出多组旅行团的有关信息（人数、上车地点、卸车地点），问汽车是否能够将全部旅行团都送到目的地。

思路：

把全部的上次地点、下车地点都存放在一个set（集合）里，命名为pos，set自动将全部地点从小到大排序，另外开两个数组dp1[1001]和dp2[1001]，dp1[i]存放的是在位置i须要上车的人数，dp2[i]存放的是在位置i须要下车的人数，dp1[i]=0表示在位置i没有人要上车，dp2[i]=0表示在位置i没有人要下车。

遍历集合pos，每到一个有上客或者下客的位置，就先下客再上客，上客的时候出现车上的人数超过容量capacity的状况就返回false。

注意：必定要先下后上！！！

上AC代码：

class Solution {
public:
    int dp1[1001];
    int dp2[1001];
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        bool ret=true;
        int num=trips.size();
        int i,j;
        set<int> pos;
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        for(i=0;i<num;i++)
        {
            dp1[trips[i][1]]+=trips[i][0];
            dp2[trips[i][2]]+=trips[i][0];
            pos.insert(trips[i][1]);
            pos.insert(trips[i][2]);
        }
        set<int>::iterator iter=pos.begin();
        int cap=0;
        while(iter!=pos.end())
        {
            int now=*iter;
            
            if(dp2[now]>0)
            {
                cap-=dp2[now];
            }
            if(dp1[now]>0)
            {
                cap+=dp1[now];
                if(cap>capacity)
                {
                    ret=false;
                    break;
                }
            }           
            iter++;
        }
        
        return ret;
    }
};