CareerCup

sort the timings (both arrival and departure )

intilaize two variables count and max equal to 0

whenever there is an arrival increment count and and when there is a departure decrement count

and at every step (increment or decrement ) compare it with max and then if count is greater than max update it .....

return max

max is nothing but the maximum no of buses going to be there at any point of time
so there need to max number of platforms

find maximum overlap count that is the answer.

Trick is to think of a domain set for time - lets say hour or minute or seconds. Below logic is for domain set "mins"

public class BusStandArrivalTimeMinPlatforms {
	
	public static void main(String[] args) {
		BusDetail[] busDetails = new BusDetail[5];
		busDetails[0]=new BusDetail(){{
			arrivalTime=10*60; //10 AM
			haltTime=20; //20 mins
		}};
		busDetails[1]=new BusDetail(){{
			arrivalTime=(int) ((10.5)*60); //10:30 AM
			haltTime=30; //30 mins
		}};
		busDetails[2]=new BusDetail(){{
			arrivalTime=11*60; //11 AM
			haltTime=15; //15 mins
		}};
		busDetails[3]=new BusDetail(){{
			arrivalTime=(int) (10.5*60); //10:30 AM
			haltTime=35; //35 mins
		}};
		busDetails[4]=new BusDetail(){{
			arrivalTime=10*60+40; //10:40 AM
			haltTime=5; //5 mins
		}};
		System.out.println("Min platforms: "+getMinPlatfoms(busDetails));
	}
	
	public static int getMinPlatfoms(BusDetail[] busDetails) {

		int domain=24*60;
		int [] slots = new int[domain];
		
		for (BusDetail busDetail : busDetails) {
			for(int i=busDetail.arrivalTime; i<busDetail.arrivalTime+busDetail.haltTime;i++){
				slots[i]++;
			}
		}
		return findMaxValue(slots);

	}
	
	public static int findMaxValue(int... array){
		assert(array.length>0);
		int max=array[0];
		for (int i : array) {
			if(max<i){
				max=i;
			}
		}
		return max;
	}
}

class BusDetail {
	public int arrivalTime;
	public int haltTime;
}

#code in python
bus_timings = [[100, 15],[110, 10], [120, 3], [122, 5], [150, 25], [150, 20], [152, 30]]

platforms = []

for arrival in bus_timings:
    found_slot = False
    for p in platforms:
        last_bus = p[-1]

        if(last_bus[0] + last_bus[1] < arrival[0]):
            p.append(arrival)
            found_slot = True
            break

    if not found_slot:
        new_platform = []
        new_platform.append(arrival)
        platforms.append(new_platform)


for p in platforms:
    print p

Calculate the time at which maximum buses are at the platform(O(nlogn) by sorting). The number of buses present at this time is the number of platforms needed.

Is the question is complete??

its a textbook problem, can be mapped directly to the 1st discussed problem of "An activity-Selection problem" of chapter Greedy Algorithms from CLRS-3rd Edition

if we have lesser domain set - say hours (24 slots) we could also use bit manipulation

Presume that every bus arrives back at 10pm and stays until the next morning at 6am. You obviously need one platform for every bus, with the information given. There need to be additional contraints to make the problem work.

Lemme assume that there are 5 bus:

/* details[x][0] contains the arrival time and and details[x][1] contains the departure time  of 5 buses where x = 0 to 4 */ 
/* starts with details[0][1] and ends in details[4][1] */
/* details[ ][ ] array can be populated in minutes as follows :
1.let us assume 24 hours clock.
2. 00:25 is equivalent to 0+25 mins.
3. similarly 10:45 will be 10*60 +45.
4. And 13:15 will be 13*60 + 45.

Note : Here am not considering the buses which arrive and leaves the next day or it stays more than a day. Yet to think a logic for it.

int MinimumPlatform( int details[5][2] )
{
     int i,j,k=0,min =1;
     for ( i = 0; i < 5; i ++)
     {
           k = 0;
           for ( j =0; j < i ; j--)
           {
                  if ( details[i][0] < details[j][1];
                  {
                           k++;
                   }
            }
            if ( k == i +1 )
            {
                  min ++;
             }
      }

return min;
}

We can use a Min Heap to solve this problem

1. Insert first arrived bus into heap (always min- heapify based on its departure time)
2. while inserting next arrived bus into heap (based on its arrival time), check whether any previosly arrived bus(es) can be removed from the heap (by comparing the currentbus.arrivaltime with MinHeaps topelement.depturetime)
3.when ever you insert an element into heap compare it with previous max_heap_size, if it is greater than max_heap_size, update max_heap_size.

max_heap_size is the minimum no: of platforms required in bus stand to hold the buses with out making them wait and with optimial use of platforms.

Efficient solution using Pair in c++

int find(int *arr,int *dep, int n){
pair<int,int> p[2*n];
int i=0,j;
for(i=0;i<n;i++){
p[2*i]=make_pair(arr[i],1);
p[2*i+1]=make_pair(dep[i],-1);
}
sort(p,p+2*n);
int tmp=0,ans=INT_MIN;
for(j=0;j<2*n;j++){
tmp+=p[j].second;
ans=max(tmp,ans);
}
return ans;
}