All problems

Corridor Desk Walk

Medium · greedy

On the first day of term, n students are standing in a long straight corridor, and n desks are placed along the same corridor. Positions are measured in metres from the door: students[i] is where student i stands and desks[j] is where desk j is. Positions are not sorted, and several students or desks may share a position.

Each student must walk to a different desk, so every desk ends up with exactly one student. All the students walk at the same time, along the corridor, so the walk for a student at position a to a desk at position b is |a - b| metres.

Choose which student goes to which desk so that the longest single walk is as short as possible, and return the length of that longest walk in metres.

Examples

Example 1

Input: students = [1, 5, 9], desks = [12, 6, 2]

Output: 3

Match 1 with 2, 5 with 6 and 9 with 12. The walks are 1, 1 and 3 metres, so the longest is 3.

Example 2

Input: students = [0, 10], desks = [10, 0]

Output: 0

Each student already stands at a desk.

Example 3

Input: students = [4], desks = [1]

Output: 3

Constraints