CareerCup

I'm assuming that there is a Booking class with an interface like

public class Booking {
  //Returns how many days in the season the guest arrives.
  public int getArrivalDate();
  //Returns how many days in the season the guest leaves.
  public int getDepartureDate();
}

I'm also assuming that the departure date must be later than the arrival date.

Here is an O(nlog(n)) solution:

boolean doIHaveEnoughRooms(int numberOfRooms, Collection<Booking> bookings) {
  return numberOfRooms >= numberOfRoomsNeeded(bookings);
}

int numberOfRoomsNeeded(Collection<Booking> bookings) {
  int n = bookings.size();
  int[] arrivals = new int[n];
  int[] departures = new int[n];
  int i = 0;
  for (int d : bookings) {
    arrivals[i] = d.getArrivalDate();
    departures[i] = d.getDepartureDate();
    ++i;
  }
  Arrays.sort(arrivals);  // Built in O(nlog(n)) sorting.
  Arrays.sort(departures); // Built in O(nlog(n)) sorting.
  int aIndex = 0;
  int dIndex = 0;
  int current = 0;  // Current number of guests.
  int max = 0;  // Max number of guests
  while (aIndex < n) {
    // You need <= instead of < if you can't use a room the same day the guest leaves.
    if (arrivals[aIndex] < departures[dIndex]) {  
      ++aIndex;
      ++current;  // Someone needs a room.
      max = Math.max(max, current);
    } else {
      ++dIndex;
      --current;  // Someone vacates a room.
    }
  }
  return max;
}

Note that the bottleneck is the sorting, everything else is simply O(n). So if you use a linear sorting algorithm instead (counting sort seems like a reasonable choice, especially if the season doesn't have too many days and you expect many people to arrive/leave on the same day), you get an O(n) algorithm.

Finding out maximum number of overlapped intervals.
if it is > no. of rooms:
then return no
else return yes

for( days in a year)
{
int a=0;
for(bookings)
{
if(day>=arrival day && day<=departure day)
a++
if( a>n)
return false
}
}
return true

it's 365(or 366)*n solution. I think it's count as O(n) solution.

A hotel manager has to process n advance bookings of rooms for the next season. His hotel has k identifical rooms. Bookings contain
an arrival date and a departure date. He wants fo find out whether there are enough rooms in the hotel to satify the demand.
Design an algorithm that solves this problem in time O(n logn) . Hint:Consider the set off all arrivals and departures .
Sort the set and process it in sorted order.
Made in Merge Sort

//assume dates can be represented by an int
	boolean enoughRooms(int capacity k; List<Bookings> bookings) {
		int[] arrivals = new int[bookings.size()];
		int[] departures = new int[bookings.size()];

		int i = 0;
		for(Booking booking: bookings) {
			arrivals[i] = booking.getArrivalTime();
			departures[i] = booking.getDepartureTime();
			i++;
		}
		PriorityQueue arrivalQueue = minHeapify(arrivals); //O(n) operation
		PriorityQueue departureQueue = minHeapify(departures);

		int roomsTaken = 0;
		//whole loops is  O(nlogn)
		while(!arrivalQueue.isEmpty()) {
			if(arrivalQueue.peek() <= departureQueue.peek()) {
				arrivalQueue.pop();
				roomsTaken++;
				if(roomsTaken > k) return false;
			} else {
				departureQueue.pop();
				roomsTaken--;
			}
		}
		return true;

		
	}