5453. 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.

Example 3:

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

Example 4:

Input: n = 9, left = [5], right = [4]
Output: 5
Explanation: At t = 1 second, both ants will be at the same intial position but with different direction.

Example 5:

Input: n = 6, left = [6], right = [0]
Output: 6

Constraints:

• 1 <= n <= 10^4
• 0 <= left.length <= n + 1
• 0 <= left[i] <= n
• 0 <= right.length <= n + 1
• 0 <= right[i] <= n
• 1 <= left.length + right.length <= n + 1
• All values of left and right are unique, and each value can appear only in one of the two arrays.

---

很有意思的一个题。一块长木板上，放了若干只蚂蚁，有的蚂蚁向左走，有的蚂蚁向右走。当两个蚂蚁碰头时，会各自掉头走。问所有蚂蚁走出木板的时间。

有点像智力题，分析了半天，发现挺简单的。想象一下，如果蚂蚁A向右走，蚂蚁B向左走，它们在坐标0点碰头了，则A掉头向左走，B掉头向右走。对于A和B来说，虽然它们的方向变了，但是对于整个木板来说，并没有差别，依然是有一只蚂蚁从0点向右走，有一只蚂蚁从0点向左走。相当于A和B交换了身份，各自帮对方走了剩下的流程。但是从宏观分析看，A和B不管掉不掉头，效果是一样的。

综上所述，完全不用考虑碰头掉头的问题，直接对向左走和向右走的蚂蚁单独分析。对于向左走的蚂蚁，最右边的蚂蚁要走最长的时间。对于向右走的蚂蚁，最左边的蚂蚁要走最长的时间。总时间就是这两种情况的最大值。代码如下：

class Solution {
public:
	int getLastMoment(int n, vector<int>& left, vector<int>& right) {
		sort(left.begin(), left.end());
		sort(right.begin(), right.end());
		int ans = 0;
		if (!left.empty())ans = max(ans, left.back());
		if (!right.empty())ans = max(ans, n - right.front());
		return ans;
	}
};

本代码提交AC。