Distance Between Bus Stops

🏠 ⬅️ ➡️

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

Example 1:

Input: distance = [1,2,3,4], start = 0, destination = 1 Output: 1 Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

Example 2:

Input: distance = [1,2,3,4], start = 0, destination = 2 Output: 3 Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

Example 3:

Input: distance = [1,2,3,4], start = 0, destination = 3 Output: 4 Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

Constraints:

  • 1 <= n <= 10^4
  • distance.length == n
  • 0 <= start, destination < n
  • 0 <= distance[i] <= 10^4
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: n, start, destination, distance(10000), min_dist
    character(len=100) :: input_string

    ! read input
    read(*, '(I5)') n
    do i = 1, n
        read(*, '(I5)') distance(i)
    end do
    read(*, '(I5)') start
    read(*, '(I5)') destination

    ! solve problem
    min_dist = solve(n, distance, start, destination)

    ! print output
    write (*, '(I5)') min_dist

contains

    function solve(n, distance, start, destination) result(min_dist)
        implicit none
        integer, intent(in) :: n, start, destination
        integer, intent(in) :: distance(n)
        integer :: i, j, k, l, min_dist

        ! initialize variables
        min_dist = huge(1_8)

        ! loop over all possible combinations of start and destination
        do i = 0, n - 1
            do j = 0, n - 1
                if (i /= j) then
                    k = modulo(j + 1, n)
                    l = modulo(k + 1, n)

                    ! check if current combination is valid
                    if ((i == start .and. j == destination) .or. &
                        (i == destination .and. j == start)) then
                        ! calculate distance
                        min_dist = min(min_dist, distance(i) + distance(j) + distance(k) + distance(l))
                    end if
                end if
            end do
        end do

        ! return solution
        min_dist = min_dist / 2
    end function solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module shortest_distance
implicit none
private
public :: shortest_distance

contains

function shortest_distance(distance, start, destination) result(shortest)
integer, intent(in) :: distance(:), start, destination
integer :: shortest

! Local variables
integer :: i, j, k, l, m, n, p, q, r, s, t, u, v, w, x, y, z
integer :: dp(size(distance))

! Initialize dp array
dp = 0

! Base case
dp(start) = 0

! Dynamic programming
do i = 1, size(distance)
    do j = 1, size(distance)
        if (i == j) then
            dp(i) = 0
        else
            dp(j) = min(dp(j), dp(i) + distance(j))
        end if
    end do
end do

! Find the shortest distance
shortest = dp(destination)

end function shortest_distance
end module

program main
use shortest_distance
implicit none

! Test cases
integer, parameter :: n = 4
integer, parameter :: distance(n) = [1, 2, 3, 4]
integer :: start, destination
integer :: shortest

! Test case 1
start = 0
destination = 1
shortest = shortest_distance(distance, start, destination)
write (*,*) "Shortest distance between 0 and 1: ", shortest

! Test case 2
start = 0
destination = 2
shortest = shortest_distance(distance, start, destination)
write (*,*) "Shortest distance between 0 and 2: ", shortest

! Test case 3
start = 0
destination = 3
shortest = shortest_distance(distance, start, destination)
write (*,*) "Shortest distance between 0 and 3: ", shortest

end program
🌐 Data from online sources 
def carPooling(trips, capacity):
    stops = [0] * 1001
    for num, start, end in trips:
        stops[start] += num
        stops[end] -= num
    for i in stops:
        capacity -= i
        if capacity < 0:
            return False
    return True
  1. Create an array stops of size 1001 (as locations are from 0 to 1000), initialized with zeros.
  2. Iterate through the trips array, and for each trip, add numPassengers to the from index and subtract numPassengers from the to index in the stops array. This will represent the number of passengers to pick up (positive value) or drop off (negative value) at each location.
  3. Iterate through the stops array, and for each location, update the capacity by subtracting the number of passengers at that location. If the capacity becomes negative at any point, return false.
  4. If we have iterated through all the locations in the stops array without the capacity becoming negative, return true. This means it's possible to pick up and drop off all passengers for all the given trips.
🌐 Data from online sources 
#include <vector>
#include <algorithm>

bool carPooling(std::vector<std::vector<int>>& trips, int capacity) {
    std::vector<int> stops(1001, 0);
    for (const std::vector<int>& t : trips) {
        stops[t[1]] += t[0];
        stops[t[2]] -= t[0];
    }
    for (int i = 0; i < stops.size(); ++i) {
        capacity -= stops[i];
        if (capacity < 0) {
            return false;
        }
    }
    return true;
}
  1. Create an array stops of size 1001 (as locations are from 0 to 1000), initialized with zeros.
  2. Iterate through the trips array, and for each trip, add numPassengers to the from index and subtract numPassengers from the to index in the stops array. This will represent the number of passengers to pick up (positive value) or drop off (negative value) at each location.
  3. Iterate through the stops array, and for each location, update the capacity by subtracting the number of passengers at that location. If the capacity becomes negative at any point, return false.
  4. If we have iterated through all the locations in the stops array without the capacity becoming negative, return true. This means it's possible to pick up and drop off all passengers for all the given trips.