CareerCup

I would do something like this:

1) Store the data like,

starting time - duration of the meeting (can use a map)

So,

8 - 3
12 - 3
15 - 3

2) Sort the input based on starting time
8 - 3
12 - 3
15 - 3

If two entries are same, then keep only the entry with largest duration.

(Eg.

If data is:
8-3
12-1
12-2
12-3
15-3 ..

then keep
8-3
12-3
15-3 ..)


3) Check for 'edge' cases:

Biz hrs: 8 - 18

read first entry: (8-3)

Cant be scheduled in the morning:

read last entry (15-3)

18 .. Cant be scheduled in the evening. Continue.

4) Now make a fresh pass, starting from 0th element

for(i -> 0:N-1)

Calculate finish time of current entry: finish_time(i)

if (start_time(i+1) - finish_time(i) >= desired_duration
return yes
else
continue

After coming out from the loop
return no

we have to fine the time interval in which all members are free
for ex 1 M1 - 8-11
m2 - 12-15
m3 - 15-18 office time is 8 to 18
have an array consisting elements 8 9 10 11 12 13 14 15 16 17 (not 18)
and now cross the hours in which any of the member is busy
here m1 8 - 11 so cross out 8 9 10 (not 11 bcoz he is free from 11)
m2 12 -15 so cross out 12 13 14 (not 15)
m3 15 - 18 so cross out 15 16 17

now find n consecutive hours which are not crossed here 11 is not crossed so we can schedule the meeting from 11 to 12

i have not done exhausted testing please check it out.

Let SD be the start of the Day and ED be the end of day.
Let S1-E1, S2-E2, S3-E3 ..... be the ranges.

Now sort all them together SD-S1-S2-S3-E2-E3-E1-S4-S5-S6-S7-E5-E6-E7-E4-ED, say it as A[0..N]

keep count=0;
for(i=1;i<N;i++)
{
if(S*) count ++; //if some meeting is starting.
if(E*) count --; //meeting ends.With time you can keep pair indicating starts or ends
if(count==0)
{
if((a[i+1]-a[i])>=D)
return i;
}
}

Frnds, what do u say abut dis simple solution...

- Restriction: Timezone is assumed to be same
- Restriction: Meeting granularity is 15 min. That is, you can't start a meeting at other than 15 min. boundary like 10:42.
- We divide the 'allowed meeting hours' into 15 min slots. 8:00 to 18:00 meeting hours (10 hours) and 4 slots per hour (15 min slot) - Resulting in 40 slot
- Keep a bitmap where each bit represents a slot.
If bit is '1', then it is busy/used
If bit is '0', then it is free
- We will convert employee's calender data into a 64-bit integer with each bit representing free/busy status (we need and use only 40 bits)
- Now do a bit operation 'OR' of all 'required employees' calender bitmaps

In the result bitmap, search for 'n' bits continuously set to '0' where 'n' is number of slots for the meeting tenure requested.

Thanks,
Laxmi

If i just find the union of the intervals (keeping min and max values for overlapped intervals), and schedule in any free interval, will it not work?

First we take first two durations, say a(s)-a(e), b(s)-b(e).
Now, we take the min start time ( a(s) or b(s) ). Let it be b(s). Now starting interval b(s) - 8. If this is greater than 1 we keep it as the start interval, b(s) - 8.

Now we take the end of the duration with min start time, in our case it is b(e) and compare it with the start of the other duration, a(s). If a(s) - b(e) > 1, our other interval is a(s) - b(e). Else no middle interval is present.

The last interval will now be 18 - max(b(e), a(e)) provided it is greater than 1. Say a(e) is the max then it is 18 -a(e).

We get three intervals, b(s) - 8, a(s) - b(e) & 18 - a(e).

Now we take each of these as the input. Say, we take first input. If c(s) - 8 > 1 or b(s) - c(e) > 1 then we divide it accordingly to get the intervals. Similarly we take each of the other inputs and find the interval suitable for us. This is next given as input to the next duration. Accordingly we find the available durations.

Another possible algo could be if we are talking only of integer values then straight away check for the time slots of 1 hour i.e 8-9 so on so forth, this way we will not need to sort. and it can be done in O(10 * n) i.e O(n) complexity, also without using any extra memory to save anything, else pallavis soln seems to be fine.

Another Method:

Scan through the employee list one by one and keep on combing their timing using the following rule :

Suppose the timing of previous employee was p(s)-p(e) and the timings of current employee is c(s)-c(e) then :

A. The two intervals are not clashing :

a. 8<------- p(s) ------ p(e) ----- c(s) -------- c(e) ---->18
= 8 <---------- p(s) -------- p(e) --------- c(s) ------- c(e) -------> (If c(s) - p(e) > 1)
If p(s) - c(e) > 1 or c(s) - p(e) > 1 then we get two intervals when the meeting cannot take place, p(s) - p(e) and c(s) - c(e).

b. 8<------- p(s) ------ p(e) ----- c(s) -------- c(e) ---->18 =
8 <------------p(s) --------------------------------------c (e) ------> (If c(s) - p(e) < 1)
If 0 < p(s) - c(e) < 1 or 0 < c(s) - p(e) < 1 then we combine the two intervals into 1 which is c(s) - p(e) or p(s) - c(e).


B. The two intervals clashes:

a. <----------- p(s) ------- c(s) ------- c(e) -------- p(e) ----------> =
<-------------p(s) ----------------------------------- p(e) ----------->
If the start and end time of 1 are inside another : As shown in fig if p(s) < c(s), c(e) < p(e) or vice versa then interval is p(s) - p(e) or c(s) - c (e).

b. < ------------ p(s) --------- c(s) ------------ p(e) --------- c(e) ---------> =
< ---------------- p(s) -------------------------------------------- c(e) ----------->
When start of one in in between the start and end of another : If p (s) < c(s) < p (e) < c(e) , the case is similar to A b. . The resulting interval if p (s) - c(e) or c(s) - p(e).

c. <------------- c(s) --------- p(s) ------------- c(e) --------- p (e) ---------> =
<----------------- c(s) ------------------------------------------ p(e) ---------->
When end of one in in between the start and end of the other : If c(s) < p(s) < c(e) < p(e) or vice versa then the interval is c(s) - p(e) or p (s) - c (e).


After obtaining a suitable interval move to the next employee . Repeat the process till are employee are covered.

Now calculate the interval in which the meeting can take place.

using System;
using System.Collections.Generic;
using System.Text;

namespace CSharp
{
	public class Class1
	{
	    struct meeting	    
	    {
	     public double start;
	     public double finish;
	    }
	    
		public static void Main(string[] args)
		{
		 meeting[] arr = new meeting[3];
		 arr[0].start = 8;
		 arr[0].finish = 13;
		 
		 arr[1].start = 10;
		 arr[1].finish = 12;
		 
		 arr[2].start = 15;
		 arr[2].finish = 17;
		 double bstart=8;
		 double bfinish=18;
		 double dur = 2;
		 
		 double maxStart=bstart;
		     double currentStart=maxStart;
		     double currentFinish=maxStart+dur;
		 
		 do{
		      currentStart=maxStart;
		      currentFinish=maxStart+dur;
			 foreach(meeting m in arr)
			 {
			   if( m.finish>maxStart &&intersect(m.start,m.finish, currentStart,currentFinish))			   
			   {
			     maxStart=m.finish;
			   }
			 }
			 
			 
		 }while(currentStart <maxStart);
		 
		 if(currentStart+dur<=bfinish)
		 System.Console.WriteLine(currentStart);
		 
		
		}
		
		static bool intersect(double s1, double f1, double s2,double f2)		
		{
		   return !(s1>=f2 || s2>=f1);
		}
	}
}