For each employee, keep track of which vacation he is assigned to, if
any.
Start with all employees unassigned.
1. Pick the first pair who have worked together and are currently
unassigned. Assign one to Trip A and the other to Trip B.
2. Loop over all pairs. If a pair are assigned to the same trip,
return failure. If one is assigned and the other is not assigned,
assign the unassigned one to the other trip.
3. If all employees are assigned, return success. If Step 2 produced
results, repeat step 2. Else return to step 1.
Don
On Aug 30, 12:13 am, ashish mann <ashishman...@gmail.com> wrote:
> Q. A company organizes two foreign trips for its employees yearly. Aim of
> the trip is to increase interaction among the employees of the company and
> hence company wants each of his employee to see new people on the trip and
> not even a single person with whom he has worked in past. Therefore it is a
> rule in company that in any of the trips, all the employees should be new
> to each other and no two of them should have worked together in past.
>
> Given the work history of each employee (which people he has worked with
> sometimes in past), you have to tell whether all of the employees can be
> accommodated within trips without violating the above rule or not. Each
> employee is given a unique integer ID by which they are recognized. You can
> also assume that each employee has worked with at least one other employee
> in past.
>
> *Note: *No employee can be in both trips and every employee must be part of
> one trip.
>
> *Example: *
>
> i) Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then
> it is possible to accommodate all the four employees in two trips (one trip
> consisting of employees 1& 3 and other having employees 2 & 4). Neither of
> the two employees in the same trip have worked together in past.
>
> ii) Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is
> no way possible to have two trips satisfying the company rule and
> accommodating all the employees.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
