[Swift]LeetCode1094. 拼车 | Car Pooling

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：http://www.noobyard.com/article/p-uqzivzum-ma.html 
➤若是连接不是山青咏芝的博客园地址，则多是爬取做者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持做者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★html

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.)node

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.git

Return true if and only if it is possible to pick up and drop off all passengers for all the given trips. github

Example 1:微信

Input: trips = [[2,1,5],[3,3,7]], capacity = 4 Output: false 

Example 2:app

Input: trips = [[2,1,5],[3,3,7]], capacity = 5 Output: true 

Example 3:post

Input: trips = [[2,1,5],[3,5,7]], capacity = 3 Output: true 

Example 4:spa

Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11 Output: true

Constraints:code

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

---

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

这儿有一份行程计划表 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

---

Runtime: 36 ms

Memory Usage: 20.9 MB

class Solution {
    func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
        var capacity = capacity
        var stops:[Int] = [Int](repeating:0,count:1001)
        for t in trips
        {
            stops[t[1]] += t[0]
            stops[t[2]] -= t[0]
        }
        var i:Int = 0
        while(capacity >= 0 && i < 1001)
        {
            capacity -= stops[i]
            i += 1
        }
        return capacity >= 0
    }
}

---

44ms

 

class Solution {
  func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
    var path = [Int].init(repeating: 0, count: 1001)
    for t in trips {
      path[t[1]] -= t[0]
      path[t[2]] += t[0]
    }
    var c = capacity
    for j in path {
      c += j
      if c < 0 {
        return false
      }
    }
    return true
  }
}

---

60ms

class Solution {
    func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
        var road = Array(repeating: 0, count: 1000)
        for trip in trips {
            let count = trip[0]
            let from = trip[1], to = trip[2]
            for pos in from..<to {
                road[pos] += count
                if road[pos] > capacity {
                    return false
                }
            }
        }
        return true
    }
}

---

68ms

class Solution {
    struct Node: Comparable {
        var addP: Int
        var location: Int
        init(_ addP:Int, _ location:Int) {
            self.addP = addP
            self.location = location
        }
        
        static func == (lhs:Node, rhs:Node) -> Bool {
            return lhs.location == rhs.location
        }
        
        static func < (lhs:Node, rhs:Node) -> Bool {
            if lhs.location == rhs.location {
                return lhs.addP < rhs.addP
            } else {
                return lhs.location < rhs.location
            }
        }
    }
    func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
        var nodes = [Node]()
        for trip in trips {
            nodes.append(Node(trip[0], trip[1]))
            nodes.append(Node(-trip[0], trip[2]))
        }
        nodes.sort()
        // print(nodes)
        var counter = 0
        for node in nodes {
            counter += node.addP
            if counter > capacity {
                return false
            }
        }
        return true
    }
}

---

80ms

class Solution {
    func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
    let finalDestination = trips.sorted{ $0[2] < $1[2]}.last![2]
    // let finalDestination = trips.last![2]
    var capacityArr = Array(repeating: 0, count: finalDestination + 1)
    
    for trip in trips {
        for journey in trip[1]..<trip[2] {
            capacityArr[journey] += trip[0]
            if capacityArr[journey] > capacity {
                return false
            }
        }
    }
    return true
  }
}