Tennis Match Scheduling

Moderate
0/80
0 upvote

Problem statement

You are an organizer for a company's tennis club. Given a list of dates where participants are unavailable, and a required number of matches M, your task is to schedule the matches on the available days.


The calendar for scheduling is determined by the input: it runs from day 1 up to the latest occupied date provided. For example, if the latest occupied date is 10, the calendar consists of days 1, 2, ..., 10.


You should schedule the M matches on the earliest available dates.


The output should be a sequence of all dates in the calendar range.


  • Unavailable dates should be represented by their number.

  • Available dates chosen for a match should be marked with an "X".

  • Available dates that are not used for a match (because M matches have already been scheduled) should be represented by their number.

If there are not enough available dates to schedule all M matches, it is impossible.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a space-separated list of integers representing the occupied dates.

The second line contains a single integer M, representing the number of match days required.


Output Format: 
If scheduling is possible, print a single line containing the resulting sequence of dates, separated by spaces.

If it is impossible to schedule M matches, print the string "Impossible".


Note: 
Using a hash set for the occupied dates will allow for efficient O(1) lookups to check if a date is available.
Sample Input 1:
2 5 6 10
4


Sample Output 1:
X 2 X X 5 6 X 8 9 10


Explanation for Sample 1:
The latest occupied date is 10, so the calendar runs from day 1 to 10.
The occupied dates are {2, 5, 6, 10}.
The available dates are {1, 3, 4, 7, 8, 9}.
We need to schedule M=4 matches. We greedily pick the first 4 available dates: 1, 3, 4, and 7.
The final schedule prints all dates from 1 to 10, marking the matches with 'X'.


Sample Input 2:
1 2 3 5 7 8 9 10
3


Sample Output 2:
Impossible


Explanation for Sample 2:
The calendar runs from 1 to 10.
The available dates are only {4, 6}.
We need to schedule M=3 matches, but only 2 dates are available. Therefore, it is impossible.


Expected Time Complexity:
The expected time complexity is O(N).


Constraints:
The list of occupied dates can contain between 0 and 1000 dates.
1 <= Occupied Date <= 1000
0 <= M <= 1000

Time limit: 1 sec
Approaches (1)
Time Complexity
Space Complexity
Code Solution
(100% EXP penalty)
Tennis Match Scheduling
Full screen
Console