College Hostel Room Allocation
The UptoSkills Arena hostel has opened for a new academic year! Students are arriving one by one. Each student wants the smallest room number that is available when they arrive. Your task is to determine which room each student will be allocated. The hostel has rooms numbered 1 to N. You are given the arrival order of M students and a list of M rooms, where the i-th room in the list is the preferred room of the student arriving i-th. If their preferred room is taken, they take the next available room. If all rooms are taken, they are left without a room (though this won't happen given the constraints).
Input
The first line contains two integers N and M, the number of rooms and the number of students, respectively. The second line contains M integers, representing the preferred room number for each student in their arrival order.
Output
Print M integers, where the i-th integer is the room number allocated to the i-th student (in arrival order).
Constraints
1 <= N <= 200000 1 <= M <= 200000 1 <= preferred_room_i <= N for all i
Example 1
5 3 2 2 4
2 3 4
Student 1 wants room 2, gets room 2. Student 2 wants room 2 (taken), gets room 3. Student 3 wants room 4, gets room 4.
Example 2
3 4 1 2 3 1
1 2 3 0
Student 1 gets 1. Student 2 gets 2. Student 3 gets 3. Student 4 wants 1 (taken), gets 4. (Assuming N=4 if M>N, but constraints say M<=N, so this case is invalid. Correcting sample input to fit constraints.) Input: 4 4 1 2 3 1 -> Output: 1 2 3 4
Hints
Similar problems
- Maximum Sum of Non-Overlapping SegmentsMedium
- Minimize Maximum Difference in PairsMedium
- Minimum Operations to Make Array SortedMedium
- Maximize Non-overlapping IntervalsMedium
- Maximum Non-overlapping IntervalsMedium
- Minimize Maximum DifferenceMedium
More topics: Sorting problems, Greedy problems, Simulation problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 2 2 4
3 4 1 2 3 1