CareerCup

greedy algorithm

this can be modeled into a graph problem.. sort the flights in order of departures.
then there is an edge between two flights if their timings are non overlapping..
after this all we need to do is to find the number of connected components in the graph.
one such component will need one stair case..
so the number of stair cases required is equal to the number of connected components in the graph..
correct me if i am thinking in the wrong direction....

Sorting by Departure Times and checking for Overlaps .

Arrival[i] and Departure[i] are the low and high of the interval i. So the problem is finding intersection of intervals.

We can use an interval tree with a slight modification such that each node represents a unique interval with a count value where no intervals intersect. When an intersection occurs during insertion if it is an exact overlap we increase the count update a max seen so far.

Else we break the intersection into 3 pieces:
left piece, intersection, right piece.

We update the intersected node as intersection and increate its count (updating a max seen), and insert the left piece and right piece.

After this max seen will be the number of stairs needed.

Its called Activity selection problem or Lecture Hall Assignment problem.

Google it to find the answer.

One simple way could be: (lets say times are upto 1 sec precision. e.g. Flight_1: 13:03:02 to 14:04:05 ..)

-- Maintain an array arr of length (24*60*60) -- to represent per second (initialize to zero)

-- Iterate over given flight times and increment each element in arr[flight_arrival_time] to arr[flight_depart_time] by 1.
e.g. for a flight with 00:00:00 - 00:05:05 - make arr[0]++, arr[1]++, ..... arr[5*60+5]++

-- max(arr) is your answer.

1. Sort by arriving time(O(nlogn))
2. scan by arriving time, for the ith earliest arriving time, calculate how many flights have already been departed, denoted as D[i]. Mark overlap[i] = i - D[i]. (O(n^2)). For example, at the time when the 3rd earliest flight arrive, if the first arrvied flight has departed but the second not, mark overlap[3] = 3 - 1 = 2
3. Find maximum D[i] (O(n))

Overall complexity O(n^2)

Cant we use the Activity Selection problem and obtain the count of the maximum non-overlapping events and then using that we could obtain the number of stairs that would be needed. Say, there are 11 flights, and we find that 5 flights are non-overlapping. In this case, the minimum number of stairs that would be needed will be 11-5+1 = 7. Can we use this approach?

we can use a method like binary search here.
suppose there are 4 planes with timings as follows...
P1- 0 - 5
P2- 4 - 8
P3- 7 - 10
P4- 0 - 10
then sort each of these according to departure time..
then we have min = 0, max = 10, suppose we use binary search so initially mid = (min + max)/2 = 5;
calculate the number of overlapping flights at this time O(n) lets call it overlap;
the maximum number of overlapping flights can be either before this mid time or after this mid time or at this time itself. Consequently, we will call two recursive calls as
maxOverlap(min, mid); => T(n/2);
maxOverlap(mid, max); => T(n/2);
Therefore, T(n) = 2*T(n/2) + O(n) = O(nlgn).
the answer will be the maximum of overlap and the value returned in the two recursive calls.

I think this will give the correct answer.
Correct me if I am wrong

can we use hashing?

<pre lang="java" line="1" title="CodeMonkey24647" class="run-this">
//Yue's algo is correct, here is the code with a minor tweak, the overlap array is not
//actually required

//ASSUMPTION- arrival array is already sorted

import java.util.Arrays;


class LadderOverlap {
public static void main (String args[]){
int arr[] = {1,2,3,3,3,4,4}; //assume sorted by arriving time
int dep[] = {2,3,5,7,6,6,7};

int D[] = new int[arr.length];
int max = 0;


for (int i=1; i < arr.length; i++){
//find how many flights have departed before i'th
for (int j=0; j<dep.length; j++){
if (dep[j]<arr[i]) D[i]++;
}

//calc the how many flights are present - ie (i'th flight - flights departed before i'th flight arrived)
if (max < (i+1 - D[i])) max = i+1 - D[i]; //we add 1 to i since its 0-based.
}

System.out.println("Departed="+Arrays.toString(D));
System.out.println("Min Ladders reqd="+max);
}
}

</pre><pre title="CodeMonkey24647" input="yes">

</pre>

<pre lang="java" line="1" title="CodeMonkey56511" class="run-this">//Copy paste error in the code above, should run now

//ASSUMPTION- arrival array is already sorted

import java.util.Arrays;


class LadderOverlap {
public static void main (String args[]){
int arr[] = {1,2,3,3,3,4,4}; //assume sorted by arriving time
int dep[] = {2,3,5,7,6,6,7};

int D[] = new int[arr.length];
//int overlap[] = new int[arr.length];
int max = 0;


for (int i=1; i < arr.length; i++){
//find how many flights have departed before i'th
for (int j=0; j<dep.length; j++){
if (dep[j]<arr[i]) D[i]++;
}


//calc the how many flights are present - ie (i'th flight - flights departed before i'th flight arrived)
if (max < (i+1 - D[i])) max = i+1 - D[i]; //we add 1 to i since its 0-based.

}

System.out.println("Departed="+Arrays.toString(D));
System.out.println("Min ladders reqd="+max);
}
}
</pre><pre title="CodeMonkey56511" input="yes">
</pre>

// This message forum doesnt handle code-comments correctly
//ASSUMPTION- arrival array is already sorted

import java.util.Arrays;


class LadderOverlap {
public static void main (String args[]){
int arr[] = {1,2,3,3,3,4,4}; //assume sorted by arriving time
int dep[] = {2,3,5,7,6,6,7};

int D[] = new int[arr.length];
//int overlap[] = new int[arr.length];
int max = 0;


for (int i=1; i < arr.length; i++){
//find how many flights have departed before i'th
for (int j=0; j<dep.length; j++){
if (dep[j]<arr[i]) D[i]++;
}

if (max < (i+1 - D[i])) max = i+1 - D[i]; //we add 1 to i since its 0-based.
}

System.out.println("Departed="+Arrays.toString(D));
System.out.println("Min ladders reqd="+max);
}
}

<pre lang="java" line="1" title="CodeMonkey49565" class="run-this">// Copy paste is breaking as this forum doesnt handle code-comments correctly.

//ASSUMPTION- arrival array is already sorted

import java.util.Arrays;


class LadderOverlap {
public static void main (String args[]){
int arr[] = {1,2,3,3,3,4,4}; //assume sorted by arriving time
int dep[] = {2,3,5,7,6,6,7};

int D[] = new int[arr.length];
int max = 0;


for (int i=1; i < arr.length; i++){
//find how many flights have departed before i'th
for (int j=0; j<dep.length; j++){
if (dep[j]<arr[i]) D[i]++;
}

//calc the how many flights are present - ie (i'th flight - flights departed before i'th flight arrived)
if (max < (i+1 - D[i])) max = i+1 - D[i]; //we add 1 to i since its 0-based.
}

System.out.println("Departed="+Arrays.toString(D));
System.out.println("ladders reqd="+max);
}
}</pre><pre title="CodeMonkey49565" input="yes">
</pre>

Here is the code, the "add runnable code" doesnt work with comments

//ASSUMPTION- arrival array is already sorted

import java.util.Arrays;


public class LadderOverlap {
	public static void main (String args[]){
		int arr[] = {1,2,3,3,3,4,4}; //assume sorted by arriving time
		int dep[] = {2,3,5,7,6,6,7};
		
		int D[] = new int[arr.length];
		int max = 0;

		
		for (int i=1; i < arr.length; i++){
			//find how many flights have departed before i'th 
			for (int j=0; j<dep.length; j++){
				if (dep[j]<arr[i]) D[i]++;
			}
			
			//calc the how many flights are present - ie (i'th flight - flights departed before i'th flight arrived)
			if (max < (i+1 - D[i])) max  = i+1 - D[i]; //we add 1 to i since its 0-based.
		}
		
		
		System.out.println("Departed="+Arrays.toString(D));
		System.out.println("Min ladders reqd="+max);
	}
}

1. combine 2 lists departure and arrival. (also keep track of which one is departure and which one is arrival. Form simple struct of time and indicator, or additional array of flag would do.
2. Sort this array based on timings (doesnt matter if its arrival or departure, just sort and also continue keeping track of whether a time is an arrival or departure time. (sort struct or swap the flags accordingly) (n or nlogn)
3. Find max# CONSECUTIVE arrivals in the array (or departures for that matter). Thats the answer.

Complexity: n or nlogn, based on the sorting method used.
3. Find max # of CONS