1503. Last Moment Before All Ants Fall Out of a Plank

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank. Example 1

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
Note that the last moment when an ant was on the plank is t = 4 second, after that it falls imediately out of the plank. (i.e. We can say that at t = 4.0000000001, there is no ants on the plank).

Example 2

Input: n = 7, left = [], right = [0,1,2,3,4,5,6,7]
Output: 7
Explanation: All ants are going to the right, the ant at index 0 needs 7 seconds to fall.

Note

1 <= n <= 10^5

题意 这个题的题意就是一群蚂蚁在一个木棍的不同点开始向左向右爬行。相碰之后,那么蚂蚁会朝向自己反方向爬行。问总共要多久,木棍是干净的。 这个题的关键点是不能模拟相碰之后的路线因为会很复杂。 因为蚂蚁移动的速度是相同的, 即便他们相碰了, 他们还是会和不相碰所处的情况一模一样。 因此,只需要求出最左端的蚂蚁和最右端的蚂蚁哪个需要更长的时间走完木棍即可。
代码

class Solution {
    public int getLastMoment(int n, int[] left, int[] right) {
        Arrays.sort(left);
        Arrays.sort(right);
        if(left.length  == 0) return n - right[0];
        if(right.length  == 0) return left[left.length - 1];
        return Math.max(n - right[0], left[left.length - 1]);
    }
}

Search

    Table of Contents