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
1second, 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 in1second). - 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
7One optimal route takes 3 seconds from [1,1] to [3,4] and 4 seconds from [3,4] to [-1,0], for a total of 7 seconds.
Example 2
Input
points = [[3,2],[-2,2]]Output
5Moving from [3,2] to [-2,2] requires 5 horizontal moves, so the minimum time is 5 seconds.
Constraints
- points.length == n
- 1 <= n <= 100
- points[i].length == 2
- -1000 <= points[i][0], points[i][1] <= 1000