LeetCode-1094 拼车

男娘i 2022-01-05 07:47 180阅读 0赞

**题目链接：**

源自LeetCode第142场周赛

[https://leetcode-cn.com/contest/weekly-contest-142/problems/car-pooling/][https_leetcode-cn.com_contest_weekly-contest-142_problems_car-pooling]

**题目描述：**

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

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

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

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

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

**示例 1：**

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

**示例 2：**

输入：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;
        }
    };

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[https_leetcode-cn.com_contest_weekly-contest-142_problems_car-pooling]: https://leetcode-cn.com/contest/weekly-contest-142/problems/car-pooling/
[20200227123106884.jpg]: /images/20211229/7ac9f9966a66484dad40f5812c23d46c.png