1094-拼車

wayneli 發布于2019-08-16 18:22 / 1504人閱讀

摘要：前言的拼車假設你是一位順風車司機，車上最初有個空座位可以用來載客。由于道路的限制，車只能向一個方向行駛也就是說，不允許掉頭或改變方向，你可以將其想象為一個向量。

前言

Weekly Contest 142的拼車：

假設你是一位順風車司機，車上最初有 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
提示：

你可以假設乘客會自覺遵守 “先下后上” 的良好素質
trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000

解題思路

本題難度為中等，主要是需要注意以下幾點：

多段路程中可能存在部分乘客下車的情況

需要考慮車子剩余的空座位

可能會存在多段路程的乘客同一個下車地點

我的解題思路如下：

將所有行程按照上車地點從小到大排序

遍歷所有行程，模擬車子行駛，使用TreeMap記錄有某個下車地點下車人數，按照以下邏輯處理

如果當前沒有乘客在車上（TreeMap為空），則判斷本次行程是否能夠讓乘客都坐下，若是將本次的行程的下車地點為key，乘客數目為value存入到TreeMap中；否則直接返回false

如果當前有乘客（TreeMap不為空），則檢查所有上車乘客是否存在需要下車的人（TreeMap中的key下車地點小于或等于本次行程的上車地點）并將其移除。然后判斷車子當前是否有足夠座位載客（TreeMap的value之和加上本次行程的乘客數是否不大于車子總座位數），如果足夠則加入本次行程（TreeMap記錄下來，如果存在相同下車地點，則人數相加），否則返回false

實現代碼

   /**
     * 1094. 拼車
     *
     * @param trips
     * @param capacity
     * @return
     */
    public boolean carPooling(int[][] trips, int capacity) {
        boolean flag = true;
        // 根據上車地點從小到大排序
        Arrays.sort(trips, Comparator.comparingInt(o -> o[1]));
        // key為下車地點，value為乘客數目
        TreeMap capacityMap=new TreeMap<>();
        for (int i = 0; i < trips.length; i++) {
            // 乘客數量
            int numPassengers = trips[i][0];
            // 上車地點
            int startLocation = trips[i][1];
            // 下車地點
            int endLocation = trips[i][2];
            if(!capacityMap.isEmpty()){
                // 處理java.util.ConcurrentModificationException
                Set locationSet = new TreeSet<>();
                locationSet.addAll(capacityMap.keySet());
                Iterator it=locationSet.iterator();
                while (it.hasNext()){
                    Integer lastEndLocation=it.next();
                    if(lastEndLocation<=startLocation){ // 到達終點，乘客下車
                        capacityMap.remove(lastEndLocation);
                    }
                }
                // 計算當前總乘客數
                int totalCap=capacityMap.values().stream().mapToInt(Integer::intValue).sum()+numPassengers;
                if(totalCap>capacity){ // 車子座位不足
                    flag=false;
                    break;
                }
                if(capacityMap.containsKey(endLocation)){ // 是否存在同一個下車地點的乘客
                    capacityMap.put(endLocation,capacityMap.get(endLocation)+numPassengers);
                }else{
                    capacityMap.put(endLocation,numPassengers);
                }
            }else{
                if (numPassengers > capacity) { // 車子座位不足
                    flag = false;
                    break;
                }
                capacityMap.put(endLocation,numPassengers);
            }
        }
        return flag;
    }

云服務器 GPU云服務器拼車

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/74972.html

記一次基于mpvue的小程序開發及上線實戰

摘要：一起打車吧微信小程序依然是一個玩具般的存在，僅供自己學習和探索，當然也歡迎各位讀者能夠貢獻代碼，參與開發小程序名稱：一起打車吧項目地址：客戶端：https://github.com/jrainlau/t... 服務端：https://github.com/jrainlau/t... 小程序二維碼：showImg(https://segmentfault.com/img/bV80...

freewolf 2019-08-22 16:32 評論0 收藏0
記一次基于mpvue的小程序開發及上線實戰

摘要：一起打車吧微信小程序依然是一個玩具般的存在，僅供自己學習和探索，當然也歡迎各位讀者能夠貢獻代碼，參與開發小程序名稱：一起打車吧項目地址：客戶端：https://github.com/jrainlau/t... 服務端：https://github.com/jrainlau/t... 小程序二維碼：showImg(https://segmentfault.com/img/bV80...

miqt 2019-07-30 16:13 評論0 收藏0
OUC2021軟件工程“e拼“校園拼車程序小組Alpha階段博客目錄

摘要：一第六周會議記錄博客鏈接第七周會議記錄博客鏈接二測試報告博客鏈接三習得的軟工原理方法技能成員收獲楊彩榮學習了如何使用進行小程序開發，以及作為一個團隊領導者，如何領導團隊進行開發李勝在本階段中我學習了和等前端知識，還學習了如何用進行團隊開一、Scrum Meeting ? ? ? ? 1.[...

buildupchao 2021-11-15 11:37 評論0 收藏0
Telegram(電報)代理MTproxy一鍵腳本

摘要：原文鏈接寫一個專門用于搭建代理的腳本支持版本如何使用復制到服務器中自動編譯安裝輸入用于客服端連接的端口號可以直接自動生成輸入一個位進制的密碼用于客服端用來驗證服務器，回車自動生成完成安裝客服端鏈接到代理服務器可以手動輸入地址，端口原文鏈接 https://github.com/shellhub/b... 寫一個專門用于搭建Telegram代理MTProxy的腳本 https://gi...

suosuopuo 2019-07-30 17:49 評論0 收藏0