Minimum Time Visiting All Points

🏠 ⬅️ ➡️

On a 2D plane, there are n points with integer coordinates points[i] = [xi, yi]. Return the minimum time in seconds to visit all the points in the order given by points.

You can move according to these rules:

  • In 1 second, you can either:
    • move vertically by one unit,
    • move horizontally by one unit, or
    • move diagonally sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second).
  • You have to visit the points in the same order as they appear in the array.
  • You are allowed to pass through points that appear later in the order, but these do not count as visits.

Example 1:

Input: points = [[1,1],[3,4],[-1,0]] Output: 7 Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
Time from [1,1] to [3,4] = 3 seconds Time from [3,4] to [-1,0] = 4 seconds Total time = 7 seconds

Example 2:

Input: points = [[3,2],[-2,2]] Output: 5

Constraints:

  • points.length == n
  • 1 <= n <= 100
  • points[i].length == 2
  • -1000 <= points[i][0], points[i][1] <= 1000
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main

! This program solves the following problem:
!
! On a 2D plane, there are n points with integer coordinates points[i] = [xi, yi].
! Return the minimum time in seconds to visit all the points in the order given by points.
!
! You can move according to these rules:
!
! - In 1 second, you can either:
!   - move vertically by one unit,
!   - move horizontally by one unit, or
!   - move diagonally sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second).
! - You have to visit the points in the same order as they appear in the array.
! - You are allowed to pass through points that appear later in the order, but these do not count as visits.
!
! Example 1:
! Input: points = [[1,1], [3,4], [-1,0]]
! Output: 7
! Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
! Time from [1,1] to [3,4] = 3 seconds
! Time from [3,4] to [-1,0] = 4 seconds
! Total time = 7 seconds
!
! Example 2:
! Input: points = [[3,2], [-2,2]]
! Output: 5
!
! Constraints:
! - points.length == n
! - 1 <= n <= 100
! - points[i].length == 2
! - -1000 <= points[i][0], points[i][1] <= 1000

implicit none

integer :: i, j, k, n, xi, yi, xj, yj, xk, yk, t, t_min
real :: d, d_min
logical :: visited(100, 100)
integer, allocatable :: points(:, :)

print '(A)', 'Enter number of points:'
read(*,*) n
allocate(points(n, 2))

do i = 1, n
    print '(A, I0, A)', 'Enter point ', i, ':'
    read(*,*) xi, yi
    points(i, :) = [xi, yi]
end do

t_min = huge(t_min)

do i = 1, n
    do j = i + 1, n
        if (.not. visited(i, j)) then
            d = sqrt((points(i, 1) - points(j, 1))**2 + (points(i, 2) - points(j, 2))**2)
            if (d < d_min) then
                d_min = d
                t = int(d_min)
            end if
        end if
    end do
end do

if (t > t_min) then
    print '(A, I0)', 'Minimum time: ', t
else
    print '(A)', 'No solution'
end if

deallocate(points)

contains

function distance(x1, y1, x2, y2) result(d)
implicit none
integer, intent(in) :: x1, y1, x2, y2
real :: d

d = sqrt((x2 - x1)**2 + (y2 - y1)**2)

end function distance

end program main
❌ Compiled
❌ Executed
❌ Correct 
module min_time_to_visit_all_points

implicit none

contains

real(kind=8) function min_time_to_visit_all_points(points) result(min_time)

! Declare variables
integer, intent(in) :: points(:, :)
integer :: n, i, j, xi, yi, xj, yj, dx, dy, d, t
real(kind=8) :: sqrt_2

! Initialize variables
n = size(points, 1)
sqrt_2 = sqrt(2.0d0)
min_time = 0.0d0

! Loop through all points
do i = 1, n - 1

    ! Get coordinates of current point
    xi = points(i, 1)
    yi = points(i, 2)

    ! Loop through all remaining points
    do j = i + 1, n

        ! Get coordinates of next point
        xj = points(j, 1)
        yj = points(j, 2)

        ! Calculate distance between current and next point
        dx = abs(xj - xi)
        dy = abs(yj - yi)
        d = max(dx, dy)

        ! Calculate time to move to next point
        if (d == 0) then
            t = 0
        else if (d == 1) then
            t = 1
        else
            t = sqrt_2
        end if

        ! Update minimum time
        min_time = max(min_time, t)

    end do

end do

end function min_time_to_visit_all_points

end module min_time_to_visit_all_points

program test_min_time_to_visit_all_points

use min_time_to_visit_all_points, only: min_time_to_visit_all_points
implicit none

! Test case 1:
print *, min_time_to_visit_all_points([[1, 1], [3, 4], [-1, 0]])
! Expected output: 7

! Test case 2:
print *, min_time_to_visit_all_points([[3, 2], [-2, 2]])
! Expected output: 5

end program test_min_time_to_visit_all_points
🌐 Data from online sources 
def minTimeToVisitAllPoints(points):
    time = 0
    for i in range(1, len(points)):
        dx = abs(points[i][0] - points[i - 1][0])
        dy = abs(points[i][1] - points[i - 1][1])
        time += max(dx, dy)
    return time

We iterate through every point in the given order. At each point, we calculate the horizontal distance dx and the vertical distance dy between the current point and the previous point. The minimum time to move between these two points is the maximum of dx and dy. This is because the diagonal movement can shorten both distances simultaneously. We add this value to the total time and continue until all points are visited.

🌐 Data from online sources 
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
    int time = 0;
    for (int i = 1; i < points.size(); i++) {
        int dx = abs(points[i][0] - points[i - 1][0]);
        int dy = abs(points[i][1] - points[i - 1][1]);
        time += max(dx, dy);
    }
    return time;
}

We iterate through every point in the given order. At each point, we calculate the horizontal distance `dx` and the vertical distance `dy` between the current point and the previous point. The minimum time to move between these two points is the maximum of `dx` and `dy`. This is because the diagonal movement can shorten both distances simultaneously. We add this value to the total time and continue until all points are visited.