Author |
Topic: Overlapping Days (Read 2134 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Overlapping Days
« on: Apr 7th, 2011, 12:54pm » |
 Quote  Modify
|
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. Any idea how to do this ?
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Overlapping Days
« Reply #1 on: Apr 7th, 2011, 2:17pm » |
Quote Modify
|
Note that you can ignore all employees such that their range covers completely another employee's range.
Then you can order the employees employee in such a way that when X arrives before Y, then X leaves before Y.
Given that order, satisfy each employee from the first to the last, assigning event days always on the last possible day(s).
That should do.
If there are 2 different programs to attend, A and B, you can alternate A and B days. If employees can attend 2 days, they can attend an A and a B event.
|
| « Last Edit: Apr 7th, 2011, 2:18pm by Grimbal » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Overlapping Days
« Reply #2 on: Apr 7th, 2011, 9:54pm » |
Quote Modify
|
on Apr 7th, 2011, 2:17pm, Grimbal wrote:Note that you can ignore all employees such that their range covers completely another employee's range.
Then you can order the employees employee in such a way that when X arrives before Y, then X leaves before Y.
Given that order, satisfy each employee from the first to the last, assigning event days always on the last possible day(s).
That should do.
If there are 2 different programs to attend, A and B, you can alternate A and B days. If employees can attend 2 days, they can attend an A and a B event.
|
|
If we are going to sort employees according to the second value (ie according to last day they will be present in organisation). Then choose last two days for the 1st emplyee and delete all the emoployees which are also present on those two days.
Do we really need to do the 1st step ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Overlapping Days
« Reply #3 on: Apr 7th, 2011, 11:07pm » |
Quote Modify
|
Given a day d, which all emplyees will be present on day day, i suppose it takes O(n) time to answer this. Is there any faster way to do it. If yes, we can solve the original problem in O(n log n).
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Overlapping Days
« Reply #4 on: Apr 8th, 2011, 6:36am » |
Quote Modify
|
Right. I was thinking aloud how to simplify the problem. You don't need to actually first remove these.
So if you order all employees by end date, and you remember the dates of the last 2 event days, you can just scan the employees in order:
- if present on the last 2 event days, he's done.
- if present on the last event day only, add a new event day on the last day of that employee (and you can forget about the oldest event day).
- if not present on either event day, add 2 event days on the last 2 days of the employee (and forget the previous event days).
That is O(n log n), because of the sorting.
PS: One additional test is that if you need to add a day, it might be the next to last, if the last day is already scheduled as an event day.
For example, if employees are present on:
1-2, 2-5, 3-5
For the 1st employee we schedule days 1,2,
for the 2nd employee we add day 5,
for the 3rd employee, we need to add one event day, but day 5, the last days, is used already.
So, whenever we add an event day, we need to schedule it on the last event-free day where the employee is there, not the last day.
|
| « Last Edit: Apr 8th, 2011, 9:58am by Grimbal » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Overlapping Days
« Reply #5 on: Apr 8th, 2011, 11:37am » |
Quote Modify
|
It will be O(n^2) since you don't know how many employees are available on a particular day.
When you decide on any two days, you have to delete all the employees which are available on those two days. This step will be O(n), simply checking each employee for availability on those two days. Can we improve on this ?
Since we have sorted them by ending date, we can't say anything about start date. So in the worst case, we have to chk every employee.
|
| « Last Edit: Apr 8th, 2011, 11:39am by birbal » |
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Overlapping Days
« Reply #6 on: Apr 8th, 2011, 12:51pm » |
Quote Modify
|
I'd keep two arrays, one with the sorted starting date of each employee, and one with the sorted ending dates (both with pointers to the employee).
Stack employees from the start array until you reach an end date, then handle all stacked employees and move onwards.
|
| « Last Edit: Apr 8th, 2011, 12:52pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Overlapping Days
« Reply #7 on: Apr 8th, 2011, 4:18pm » |
Quote Modify
|
No (to birbal). Once you have sorted the employee by end date, you just take each one in turn and add 1 or 2 days at the end as necessary. You only need to compare an employee's range with the last 2 days in the schedule so far.
The sorting is O(n log n), the processing is O(n).
Code:Arrays.sort(employees, orderByLastDay);
List<Integer> events = new ArrayList<Integer>();
for( int[] emp : employees ){
int size = events.size();
if( size<2 || events.get(size-1)<emp[0]){
events.add(emp[1]-1);
events.add(emp[1]);
} else
if( events.get(size-2)<emp[0] ){
if( events.get(size-1)==emp[1] ){
events.remove(size-1);
events.add(emp[1]-1);
}
events.add(emp[1]);
}
} |
|
|
| « Last Edit: Apr 8th, 2011, 6:30pm by Grimbal » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Overlapping Days
« Reply #8 on: Apr 9th, 2011, 9:21am » |
Quote Modify
|
on Apr 8th, 2011, 4:18pm, Grimbal wrote:No (to birbal). Once you have sorted the employee by end date, you just take each one in turn and add 1 or 2 days at the end as necessary. You only need to compare an employee's range with the last 2 days in the schedule so far.
The sorting is O(n log n), the processing is O(n).
Code:Arrays.sort(employees, orderByLastDay);
List<Integer> events = new ArrayList<Integer>();
for( int[] emp : employees ){
int size = events.size();
if( size<2 || events.get(size-1)<emp[0]){
events.add(emp[1]-1);
events.add(emp[1]);
} else
if( events.get(size-2)<emp[0] ){
if( events.get(size-1)==emp[1] ){
events.remove(size-1);
events.add(emp[1]-1);
}
events.add(emp[1]);
}
} |
|
|
|
Nice solution. It works. I interpreted it wrongly earlier.
If the days are like days of a month or year, then we can even sort in O(n) using bucket sort.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print