CareerCup

Preserving white space

My Solution goes like this:

1. Sort the timings and maintain the schedules as follows
   9:00 9:15 9:30 10:00 10:00  10:15 10:20 10:25 11:00 11:10 11:15 11:20
    S    S    S     E     E      E     S     S     S     E     E      E

 
   Here S - Start time and E- End time. (If both the times are equal, first keep end time and then start time)
2. For this set 1 for S and -1 for E and find out cumulative sum

   9:00 9:15 9:30 10:00 10:00  10:15 10:20 10:25 11:00 11:10 11:15 11:20
    S    S    S     E     E      E     S     S     S     E     E      E
    1    1    1     -1    -1     -1    1     1     1     -1    -1     -1
    1    2    3     2      1      0    1     2     3      2     1      0

This shows at every time slot who are all the employees in the meeting. A value 0 implies that no body is having meeting in that particular slot.

In the above example; Slot between 10:15 - 10:20 is free and they are all free after 11:20 only

Any better solutions than this?

My Solution goes like this:

1. Sort the timings and maintain the schedules as follows
9:00 9:15 9:30 10:00 10:00 10:15 10:20 10:25 11:00 11:10 11:15 11:20
S S S E E E S S S E E E


Here S - Start time and E- End time. (If both the times are equal, first keep end time and then start time)
2. For this set 1 for S and -1 for E and find out cumulative sum

9:00 9:15 9:30 10:00 10:00 10:15 10:20 10:25 11:00 11:10 11:15 11:20
S S S E E E S S S E E E
1 1 1 -1 -1 -1 1 1 1 -1 -1 -1
1 2 3 2 1 0 1 2 3 2 1 0

This shows at every time slot who are all the employees in the meeting. A value 0 implies that no body is having meeting in that particular slot.

In the above example; Slot between 10:15 - 10:20 is free and they are all free after 11:20 only

Any better solutions than this?

Another solution is just sorting the pairs of numbers as following.
For two pairs, p1 and p2
If p2.start > p1.end then p2 > p1
If p2.end < p1.start then p2 < p1

Otherwise merge these two pairs as

p3.start = min(p1.start, p2.start)
p3.end = max(p1.end, p2.end)

at the end of this procedure we will have the array of sorted pairs, and available time slots would be (p[i].end, p[i+1].start)

For the example above, the resulting array would be

{<9:00, 10:15>, <10:20, 11:20>}

So, the timeslots would be
<10:15, 10:20> and <11:20, ~>

Can be done in the same way as given in link in the name field above

/*
 * en.wikipedia.org/wiki/Greedy_algorithm, en.wikipedia.org/wiki/Activity_selection_problem
 * personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/actSelectionGreedy.htm
 */
public class ActivityScheduling {
	class User{String userid;}
	class Venue{String venueid;}
	class Activity{
		float startTime;
		float endTime;
		String avtivityId;
		/*	List<User> users; 
			Venue venue;// fix_me depending on OneToMany 
		 */
		public Activity(float startTime, float endTime, String avtivityId) {
			this.startTime= startTime; 
			this.endTime= endTime;
			this.avtivityId=avtivityId;
		}
		
	}
	Activity[] acts; User[] users; Venue[] venues;
	int maxSchedules=0; 
	float startTime=0; // intitialise this first endiTime and iterate from 2 to n
	public void prepareDate(int noOfActivities, float[] startTimes, float[] endTimes, String[] activites){
		acts = new Activity[noOfActivities];		
		for(int i=0; i <noOfActivities; i++ ){
			acts[i] = new Activity(startTimes[i],endTimes[i], activites[i] );
		}
		Arrays.sort(acts, new Comparator<Activity>(){
			// sort as per the ENDTIME
			public int compare(Activity a1, Activity a2) {				
				if( a1.endTime > a2.endTime) return 1;
				else if( a1.endTime < a2.endTime)return -1;
				else return 0;
			}
			
		});
	}	
	public void getMaxSchedules(){
		Activity act;
		for(int i =0; i < acts.length; i++){
			act = acts[i];
			if(act.endTime > startTime){
				System.out.printf("Activity startTime:" + act.startTime +", endTime:"+ act.endTime+"\n");
				maxSchedules++;
				startTime = act.endTime;
			}
		}
		System.out.printf("Maximun no of Activities:" + maxSchedules);
		return;		
	}
}