This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

describe

There are n seats and n students in a room. You are given an array seats of length n, where seats[i] is the position of the ith seat. You are also given the array students of length n, where students[j] is the position of the jth student.

You may perform the following move any number of times:

Increase or decrease the position of the ith student by 1 (i.e., moving the ith student from position x to x + 1 or x – 1) Return the minimum number of moves required to move each student to a seat such that no two students are in the same seat.

Note that there may be multiple seats or students in the same position at the beginning.

Example 1:

Input: seats = [3,1,5], students = [2,7,4] Output: 4 Explanation: The students are moved as follows: - The first student is moved from from position 2 to position 1 using 1 move. - The second student is moved from from position 7 to position 5 using 2 moves. - The third student is moved from from position 4 to position 3 using 1 move. In  total, 1 + 2 + 1 = 4 moves were used.Copy the code

Example 2:

Input: seats = [4,1,5,9], students = [1,3,2,6]
Output: 7
Explanation: The students are moved as follows:
- The first student is not moved.
- The second student is moved from from position 3 to position 4 using 1 move.
- The third student is moved from from position 2 to position 5 using 3 moves.
- The fourth student is moved from from position 6 to position 9 using 3 moves.
In total, 0 + 1 + 3 + 3 = 7 moves were used.
Copy the code

Example 3:

Input: seats = [2,2,6,6], students = [1,3,2,6]
Output: 4
Explanation: The students are moved as follows:
- The first student is moved from from position 1 to position 2 using 1 move.
- The second student is moved from from position 3 to position 6 using 3 moves.
- The third student is not moved.
- The fourth student is not moved.
In total, 1 + 3 + 0 + 0 = 4 moves were used.
Copy the code

Note:

n == seats.length == students.length
1 <= n <= 100
1 <= seats[i], students[j] <= 100
Copy the code

parsing

Seats [I] seats[I] seats[I] Seats [I] Seats [I] Seats [I] Seats [I] Seats [I] Seats [I] Seats [I] Seats

  • Move a student to add or subtract a seat number, for example, move a student from seat number 3 to seat number 2 or 4

How many times do we need to do the above operation? We can arrange all students in the seats, and no two students sit in the same seat. In fact, the idea is very simple, is to find a rule of the problem.

Assuming seats = [12,14,19,19,12] and students = [19,2,17,20,7], we can get:

Seats = [12,12,14,19,19] students = [2,7,17,19,20]Copy the code
  • We can find that the nearest seat number of students[0] is seats[0]. Seats [1] and the seats behind it must be equal or farther away without considering. In this case, seats[0] is occupied
  • Seats [1] Seats [0] Seats [1] Seats [0] Seats [1]
  • Seats [2] and the seat behind it must be equal or farther. However, seats[0] is already occupied, so the nearest seat is seats[1]
  • Students [2] students nearest seat number is seats [1] and seats [2].
  • Seats [3] and the seat behind it must be equal or farther. However, seats[1] is already occupied, so the nearest seat is seats[2]
  • We find that the seat of seats[I] of the same index I is the nearest seat of students[I]. The result can be obtained by adding ABS (seats[I]-students[I]) directly into the result.

answer

class Solution(object):
    def minMovesToSeat(self, seats, students):
        """
        :type seats: List[int]
        :type students: List[int]
        :rtype: int
        """
        result = 0
        seats.sort()
        students.sort()
        save = []
        for i in range(len(seats)):
            result += abs(seats[i]-students[i])
        return result
        	      
		
Copy the code

The results

Runtime: 10 ms, faster than 100.00% of Python online submissions for Minimum Number of Moves to Seat Everyone. Memory Usage: Submissions in Python online submissions for Minimum Number of Moves to Seat Everyone.Copy the code

Original link: leetcode.com/problems/mi…

Your support is my biggest motivation