1266. Minimum Time Visiting All Points #

Problem #

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

• In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
• You have to visit the points in the same order as they appear in the array.

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

Problem Summary #

There are n points on a plane, and the positions of the points are represented by integer coordinates points[i] = [xi, yi]. Please calculate the minimum time needed to visit all these points (in seconds). You can move on the plane according to the following rules:

• Each second, move one unit horizontally or vertically, or move diagonally (which can be seen as moving one unit horizontally and one unit vertically within one second).
• The points must be visited in the order they appear in the array.

Note:

• points.length == n
• 1 <= n <= 100
• points[i].length == 2
• -1000 <= points[i][0], points[i][1] <= 1000

Solution Ideas #

• Given an array on the Cartesian coordinate system, the points in the array are the points the plane passes through during its flight. The plane can only fly horizontally, vertically, or at a 45° angle. Ask for the shortest time for the plane to pass through all points.
• A simple math problem. Traverse the array in order, calculate the differences on the x-axis and y-axis separately, and take the maximum value, which is the shortest flight time between the two points. Finally, accumulating the maximum value calculated each time gives the shortest time.

Code #

package leetcode

func minTimeToVisitAllPoints(points [][]int) int {
	res := 0
	for i := 1; i < len(points); i++ {
		res += max(abs(points[i][0]-points[i-1][0]), abs(points[i][1]-points[i-1][1]))
	}
	return res
}