“This is the 27th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

The question to describe

Let’s say you’re a hitchhiker with an initial capacity of empty seats for passengers. A car can only go in one direction due to road constraints (that is, it is not allowed to turn around or change direction, you can think of it as a vector).

Trips [I] = [num_passengers, start_location, end_location] trips[][] trips[I] = [num_passengers, start_location, end_location] trips[]

  • The number of passengers that have to be picked up and dropped off;
  • The boarding place of the passenger;
  • And where the passengers get off.

The locations given are the distances required to travel from your initial starting position to these locations (they must be in your driving direction).

Use the given itinerary and the number of seats to determine if your car can successfully pick up and remove all passengers (return true if and only if you can pick up and remove all passengers on any given trip, otherwise return false).

Example 1:

Trips = [[2,1,5],[3,3,7]], capacity = 4 output: false

Example 2:

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

Solution 1: Difference array +Map

A difference array, as we all know, is a variation of the prefix and. We regard getting on and off the bus at different stations as adding and subtracting numbers in different ranges of the difference array. Finally, count the number of people at each site, return false if the number exceeds the threshold, and since you only need to judge, the number of people can be stored without an array. Space complexity is also saved.

var carPooling = function(trips, capacity) {
  const map = {};
  for (const trip of trips) {
    const [ passengers, start, end ] = trip;
    for (let index = start; index < end; index++) {
      map[index] = map[index] ? map[index] + passengers : passengers;
      if (map[index] > capacity) {
        return false; }}}return true;
};
Copy the code
Solution 2: Greed

(TRIPS [I][1]) (trips[I][1]) (trips[I][1]) (trips[I][1]) (TRIPS [I][1]) (TRIPS [I][1])

var carPooling = function(trips, capacity) {
    trips.sort((a,b) = >a[1]-b[1])
    let num=0,result=true
    let  Cars={}
    for(i=0; i<trips.length; i++){for(key in  Cars){
            if(key<=trips[i][1]){
                num-= Cars[key]
                delete  Cars[key]
            }
        }
        num+=trips[i][0]
         Cars[trips[i][2]]= Cars[trips[i][2]]? Cars[trips[i][2]]+=trips[i][0]:trips[i][0]
        if(num>capacity){
            result=false
            break}}return result
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤