CareerCup

We can convert this to a bin packing problem which can be solved using a Max Winner tree. Complexity is O(log n).

Hi,
Can you please explain more about the question like, what do the numbers 4, (3,1) , (2,2) indicate?
Thanks in advance

/*
* BusSeat.cpp
*
* Created on: Dec 10, 2012
* Author: Kevin Li
*/


#include <cstdio>
#include <iostream>
using namespace std;
//This is the available seats in each row
int seatRow[10]={3,1,2,2,1,1,2,1,2,1};
bool flag=false;
//check if there is enough seat n for the request
bool seatsAvailable(int n)
{
for(int i =0; i< 10; i++)
{
if(seatRow[i]>=n)
{
seatRow[i]-=n;
return true;
}
}
return false;
}

int getSeat(int total,int n)
{
//check if request seat number available
if(seatsAvailable(n))
{
cout<<"get seat number"<<n<<endl;
if(total>n)
{
//if there is still more seat needed, search them
getSeat(total-n,total-n);
}
return 0;
}
else
{
int seat =getSeat(total,n-1);
}
return 0;
}

naga-programming-concepts.blogspot.in/2012/12/bus-reseravation-httpwwwcareercupcomque.html

This should work,although doing lot more than required.

#include <stdio.h>
#include <stdlib.h>

const int R=10;
const int C=6;

int gettotal(int *seats,int size)
{
	int i,sum=0;
	for(i=0;i<size;i++)
		sum+=seats[i];
	return sum;
}

main()
{
	int seats[R];
	int i,num,start,end,j,max=0,index=-1,available;
	char c;
	for(i=0;i<R;i++)
		seats[i]=C;
	do
	{
		printf("No. of tickets:\n");
		scanf("%d",&num);
		for(i=0;i<R;i++)
		{
			available=gettotal(seats,R);
			if(num>available)
			{
				printf("\n#####Only %d seats available#####\n",available);
				break;
			}
			if(seats[i]>=num)
			{
				start=C-seats[i]+1;
				end=start+num-1;
				printf("\t%d seats allotted at row %d seat %d-%d.\n",num,i,start,end);
				seats[i]=seats[i]-num;
				for(j=0;j<R;j++)
					printf("%d ",seats[j]);
				printf("\n");
				break;
			}
			else
			{
				if(seats[i]>max)
				{
					max=seats[i];
					index=i;
				}
				if(i==R-1)
				{
					start=C-seats[index]+1;
					end=start+max-1;
					printf("\t..%d seats allotted at row %d seat %d-%d.\n",max,index,start,end);
					seats[index]=seats[index]-max;
					num=num-max;
					for(j=0;j<R;j++)
						printf("%d ",seats[j]);
					printf("\n");
					i=-1;
					max=0,index=-1;
				}

			}
		}
		// for(j=0;j<R;j++)
		// 	printf("%d ",seats[j]);
		if(gettotal(seats,R)==0)
		{
			printf("\nNO MORE ALLOCATION POSSIBLE.. QUITTING\n");
			break;
		}
		printf("\nCONTINUE?y[n]: ");
		c=getchar();
		c=getchar();
	}while(c!='n');
}

onestopinterviewprep.blogspot.com/2014/03/bus-seat-reservation.html