Thursday, March 17, 2011

Event Scheduling for N Employees in a month

You are given N ranges of date offsets when N employees are present in an organization. Something like
1-4 (i.e. employee will come on 1st, 2nd, 3rd and 4th day )
2-6
8-9
..
1-14
You have to organize an event on minimum number of days such that each employee can attend the event at least twice.


APPROACH:
All employees have to attend atleast 2 times.
So I keep a count of 2 for every employee initially.


Then I initialize an array (days) of 30 days maintaining a count of number of employees who can attend on a particular day.


I take the maximum of the days array. For all the employees, who can attend on that day I reduced their counts in the first array.
When the count becomes zero for any employee, I delete him from the days array.


I keeping running this loop until all employees have count <=0.
Input via console: N (no. of Employees) and then N rows of ranges corresponding to the N employees.
Sample Input:

15
2 4
3 8
5 20
24 30
1 10
9 15
19 23
20 30
1 5
2 10
1 15
1 10
5 25
15 30
7 17
Sample output:

Printing event days: 
5
7
15
20
21
3
4
25
24
9

No comments:

Post a Comment