資訊專欄INFORMATION COLUMN
摘要：前言的拼車假設(shè)你是一位順風(fēng)車司機(jī)，車上最初有個(gè)空座位可以用來(lái)載客。由于道路的限制，車只能向一個(gè)方向行駛也就是說(shuō)，不允許掉頭或改變方向，你可以將其想象為一個(gè)向量。
前言
Weekly Contest 142的 拼車：
解題思路假設(shè)你是一位順風(fēng)車司機(jī)，車上最初有 capacity 個(gè)空座位可以用來(lái)載客。由于道路的限制，車 只能 向一個(gè)方向行駛（也就是說(shuō)，不允許掉頭或改變方向，你可以將其想象為一個(gè)向量）。
這兒有一份行程計(jì)劃表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了你的第 i 次行程信息：
必須接送的乘客數(shù)量；
乘客的上車地點(diǎn)；
以及乘客的下車地點(diǎn)。
這些給出的地點(diǎn)位置是從你的 初始 出發(fā)位置向前行駛到這些地點(diǎn)所需的距離（它們一定在你的行駛方向上）。
請(qǐng)你根據(jù)給出的行程計(jì)劃表和車子的座位數(shù)，來(lái)判斷你的車是否可以順利完成接送所用乘客的任務(wù)（當(dāng)且僅當(dāng)你可以在所有給定的行程中接送所有乘客時(shí)，返回 true，否則請(qǐng)返回 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提示：
你可以假設(shè)乘客會(huì)自覺遵守 “先下后上” 的良好素質(zhì)
trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000
本題難度為中等，主要是需要注意以下幾點(diǎn)：
多段路程中可能存在部分乘客下車的情況
需要考慮車子剩余的空座位
可能會(huì)存在多段路程的乘客同一個(gè)下車地點(diǎn)
我的解題思路如下：
將所有行程按照上車地點(diǎn)從小到大排序
遍歷所有行程，模擬車子行駛，使用TreeMap記錄有某個(gè)下車地點(diǎn)下車人數(shù)，按照以下邏輯處理
如果當(dāng)前沒有乘客在車上（TreeMap為空），則判斷本次行程是否能夠讓乘客都坐下，若是將本次的行程的下車地點(diǎn)為key，乘客數(shù)目為value存入到TreeMap中；否則直接返回false
如果當(dāng)前有乘客（TreeMap不為空），則檢查所有上車乘客是否存在需要下車的人（TreeMap中的key下車地點(diǎn)小于或等于本次行程的上車地點(diǎn)）并將其移除。然后判斷車子當(dāng)前是否有足夠座位載客（TreeMap的value之和加上本次行程的乘客數(shù)是否不大于車子總座位數(shù)），如果足夠則加入本次行程（TreeMap記錄下來(lái)，如果存在相同下車地點(diǎn)，則人數(shù)相加），否則返回false
實(shí)現(xiàn)代碼 /**
* 1094. 拼車
*
* @param trips
* @param capacity
* @return
*/
public boolean carPooling(int[][] trips, int capacity) {
boolean flag = true;
// 根據(jù)上車地點(diǎn)從小到大排序
Arrays.sort(trips, Comparator.comparingInt(o -> o[1]));
// key為下車地點(diǎn)，value為乘客數(shù)目
TreeMap capacityMap=new TreeMap<>();
for (int i = 0; i < trips.length; i++) {
// 乘客數(shù)量
int numPassengers = trips[i][0];
// 上車地點(diǎn)
int startLocation = trips[i][1];
// 下車地點(diǎn)
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){ // 到達(dá)終點(diǎn)，乘客下車
capacityMap.remove(lastEndLocation);
}
}
// 計(jì)算當(dāng)前總乘客數(shù)
int totalCap=capacityMap.values().stream().mapToInt(Integer::intValue).sum()+numPassengers;
if(totalCap>capacity){ // 車子座位不足
flag=false;
break;
}
if(capacityMap.containsKey(endLocation)){ // 是否存在同一個(gè)下車地點(diǎn)的乘客
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;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/74972.html
摘要：一起打車吧微信小程序依然是一個(gè)玩具般的存在，僅供自己學(xué)習(xí)和探索，當(dāng)然也歡迎各位讀者能夠貢獻(xiàn)代碼，參與開發(fā) 小程序名稱：一起打車吧 項(xiàng)目地址：客戶端：https://github.com/jrainlau/t... 服務(wù)端：https://github.com/jrainlau/t... 小程序二維碼：showImg(https://segmentfault.com/img/bV80...
摘要：一起打車吧微信小程序依然是一個(gè)玩具般的存在，僅供自己學(xué)習(xí)和探索，當(dāng)然也歡迎各位讀者能夠貢獻(xiàn)代碼，參與開發(fā) 小程序名稱：一起打車吧 項(xiàng)目地址：客戶端：https://github.com/jrainlau/t... 服務(wù)端：https://github.com/jrainlau/t... 小程序二維碼：showImg(https://segmentfault.com/img/bV80...
摘要：一第六周會(huì)議記錄博客鏈接第七周會(huì)議記錄博客鏈接二測(cè)試報(bào)告博客鏈接三習(xí)得的軟工原理方法技能成員收獲楊彩榮學(xué)習(xí)了如何使用進(jìn)行小程序開發(fā)，以及作為一個(gè)團(tuán)隊(duì)領(lǐng)導(dǎo)者，如何領(lǐng)導(dǎo)團(tuán)隊(duì)進(jìn)行開發(fā)李勝在本階段中我學(xué)習(xí)了和等前端知識(shí)，還學(xué)習(xí)了如何用進(jìn)行團(tuán)隊(duì)開 一、Scrum Meeting ? ? ? ? 1.[...
摘要：原文鏈接寫一個(gè)專門用于搭建代理的腳本支持版本如何使用復(fù)制到服務(wù)器中自動(dòng)編譯安裝輸入用于客服端連接的端口號(hào)可以直接自動(dòng)生成輸入一個(gè)位進(jìn)制的密碼用于客服端用來(lái)驗(yàn)證服務(wù)器，回車自動(dòng)生成完成安裝客服端鏈接到代理服務(wù)器可以手動(dòng)輸入地址，端口 原文鏈接 https://github.com/shellhub/b... 寫一個(gè)專門用于搭建Telegram代理MTProxy的腳本 https://gi...
閱讀 2227·2021-11-18 10:02
閱讀 3318·2021-11-11 16:55
閱讀 2722·2021-09-14 18:02
閱讀 2475·2021-09-04 16:41
閱讀 2122·2021-09-04 16:40
閱讀 1255·2019-08-30 15:56
閱讀 2254·2019-08-30 15:54
閱讀 3189·2019-08-30 14:15
