문제
You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)
Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle’s initial location.
Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.
제한사항
- trips.length <= 1000
- trips[i].length == 3
- 1 <= trips[i][0] <= 100
- 0 <= trips[i][1] < trips[i][2] <= 1000
- 1 <= capacity <= 100000
입출력 예
1
2
3
4
| Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
|
1
2
3
4
| Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
|
1
2
3
4
| Example 3:
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true
|
1
2
3
4
| Example 4:
Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true
|
풀이
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
| func carPooling(trips [][]int, capacity int) bool {
// 시작지점(trips[i][1]) 기준으로 정렬
sort.SliceStable(trips, func(i, j int) bool {
if trips[i][1] == trips[j][1] {
return trips[i][2] < trips[j][2]
} else {
return trips[i][1] < trips[j][1]
}
})
var passengerCount = 0
for i, item := range trips {
// 현재 index 이전의 path를 조사하는데,
// 현재 index의 시작지점이 이전 index의 도착지점보다 크다면
// 이미 도착지점이 지난것 이므로 도착지점에 도착한 승객을 뺌
// 내린 승객을 중복으로 계산하지 않도록 0을 대입
for j := 0 ; j < i ; j++ {
if item[1] >= trips[j][2] {
passengerCount -= trips[j][0]
trips[j][0] = 0
}
}
// 현재 탑승하는 승객을 더해 용량보다 큰지 검사
passengerCount += item[0]
if passengerCount > capacity {
return false
}
}
return true;
}
|
