Move Students to Desks
EasyGreedy
Problem
An exam hall has desks in a single row at positions desks, and the same number of students standing at positions students. Moving one student one position left or right costs one step.
Seat every student at a different desk. Return the minimum total number of steps. Several desks or students may share a position initially.
Example 1
- Input:
- desks = [3, 1, 5], students = [2, 7, 4]
- Output:
- 4
Student at 2 → desk 1 (1 step), 4 → 3 (1 step), 7 → 5 (2 steps).
Example 2
- Input:
- desks = [4, 1, 5, 9], students = [1, 3, 2, 6]
- Output:
- 7
Constraints
- 1 ≤ desks.length = students.length ≤ 10^4
- 0 ≤ desks[i], students[j] ≤ 10^5
Hint
Show the first hint
Should the leftmost student ever end up at a desk to the right of where the second-leftmost student sits?
Walkthrough
How to approach it
01Clarify before coding
- Is the number of desks equal to the number of students? Yes.
- Can students pass through each other or share a position while moving? Yes, only final seats must be distinct desks.
- Is the cost just the sum of distances? Yes, each student walks straight to their desk.
02Brute force
Try all n! assignments of students to desks and take the cheapest.
Cost: O(n! · n): hopeless beyond about 10 students.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.