[Swift]LeetCode1094.拼车|CarPooling

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/11032164.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle onlydrives 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.

Example 1:

Input: trips = 4
Output: false

Example 2:

Input: trips = 5
Output: true

Example 3:

Input: trips = 3
Output: true

Example 4:

Input: trips = 11
Output: true

Constraints:

trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000

假设你是一位顺风车司机，车上最初有 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

Runtime: 36 ms

Memory Usage: 20.9 MB

 1 class Solution {
 2     func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
 3         var capacity = capacity
 4         var stops:[Int] = [Int](repeating:0,count:1001)
 5         for t in trips
 6         {
 7             stops[t[1]] += t[0]
 8             stops[t[2]] -= t[0]
 9         }
10         var i:Int = 0
11         while(capacity >= 0 && i < 1001)
12         {
13             capacity -= stops[i]
14             i += 1
15         }
16         return capacity >= 0
17     }
18 }

44ms

 1 class Solution {
 2   func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
 3     var path = [Int].init(repeating: 0, count: 1001)
 4     for t in trips {
 5       path[t[1]] -= t[0]
 6       path[t[2]] += t[0]
 7     }
 8     var c = capacity
 9     for j in path {
10       c += j
11       if c < 0 {
12         return false
13       }
14     }
15     return true
16   }
17 }

60ms

 1 class Solution {
 2     func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
 3         var road = Array(repeating: 0, count: 1000)
 4         for trip in trips {
 5             let count = trip[0]
 6             let from = trip[1], to = trip[2]
 7             for pos in from..<to {
 8                 road[pos] += count
 9                 if road[pos] > capacity {
10                     return false
11                 }
12             }
13         }
14         return true
15     }
16 }

68ms

 1 class Solution {
 2     struct Node: Comparable {
 3         var addP: Int
 4         var location: Int
 5         init(_ addP:Int, _ location:Int) {
 6             self.addP = addP
 7             self.location = location
 8         }
 9         
10         static func == (lhs:Node, rhs:Node) -> Bool {
11             return lhs.location == rhs.location
12         }
13         
14         static func < (lhs:Node, rhs:Node) -> Bool {
15             if lhs.location == rhs.location {
16                 return lhs.addP < rhs.addP
17             } else {
18                 return lhs.location < rhs.location
19             }
20         }
21     }
22     func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
23         var nodes = [Node]()
24         for trip in trips {
25             nodes.append(Node(trip[0], trip[1]))
26             nodes.append(Node(-trip[0], trip[2]))
27         }
28         nodes.sort()
29         // print(nodes)
30         var counter = 0
31         for node in nodes {
32             counter += node.addP
33             if counter > capacity {
34                 return false
35             }
36         }
37         return true
38     }
39 }

80ms

 1 class Solution {
 2     func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
 3     let finalDestination = trips.sorted{ $0[2] < $1[2]}.last![2]
 4     // let finalDestination = trips.last![2]
 5     var capacityArr = Array(repeating: 0, count: finalDestination + 1)
 6     
 7     for trip in trips {
 8         for journey in trip[1]..<trip[2] {
 9             capacityArr[journey] += trip[0]
10             if capacityArr[journey] > capacity {
11                 return false
12             }
13         }
14     }
15     return true
16   }
17 }