Hotel Bookings Bookings Possible
<p>I have implemented a short algorithm that tells whether all hotel bookings are possible or not. The problem is very similar to <a href="http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/" rel="nofollow">this</a>, but I have tried to implement my own logic.</p>

<p>(Very sorry for such long explaination)</p>

<p>In my algorithm</p>

<ol>
<li><code>int</code> K= Number of rooms available </li>
<li><code>ArrayList&lt;Integer&gt;</code> arrive = Arrival time of guest </li>
<li><code>ArrayList&lt;Integer&gt;</code> depart = Departure time of guest</li>
<li><code>int</code> arriving_guest = Next guest</li>
<li><code>ArrayList&lt;ArrayList&lt;Integer&gt;&gt;</code> arrange = allocation of rooms</li>
</ol>

<p>For example </p>

<ul>
<li>arrive = [1,3,5]</li>
<li>depart = [2,6,8] and </li>
<li>K=1</li>
</ul>

<p>Now before we begin to iterate the <strong><code>ArrayList&lt;ArrayList&lt;Integer&gt;&gt; arrange</code> will be <code>[[2]]</code> as initially all rooms are available and <code>int arriving_guest = 1</code> as first guest is accommodated it will point to the next guest</strong></p>

<p>Now for 1st iteration, where the guest's arrival time is 3 and departure time is 6</p>

<ul>
<li>Check whether the first room is available </li>
<li>As the first guest departure time is 2 so his room can be given to 2nd guest so <code>arrange</code> will become <code>[[2,6]]</code></li>
<li>Increment <code>arriving_guest</code> to point to next guest</li>
</ul>

<p>Now for 2nd iteration, where the guest's arrival time is 5 and departure time is 8</p>

<ul>
<li>Check whether the first room is available </li>
<li>As the 2nd guest departure time is 6 so his room cannot be given to 3rd guest so a new room should be allocated for 3rd guest and <code>arrange</code> will become <code>[[2,6],[8]]</code></li>
<li>Increment <code>arriving_guest</code> to point to next guest</li>
</ul>

<p>At the end of the algorithm</p>

<p>Rooms needed = <code>arrange.size()</code> = 2</p>

<p>Rooms available = <code>K</code> = 1</p>

<p>So it will return <code>false</code> value for above</p>

<p><strong>If I apply my algorithm for the below test case it fails</strong></p>

<ul>
<li>arrive : [ 14, 29, 0, 35, 34, 15, 17, 7, 28, 13, 40, 28, 11, 40 ]</li>
<li>depart : [ 51, 77, 37, 63, 76, 25, 57, 23, 40, 32, 63, 41, 21, 68 ]</li>
<li>K : 9</li>
</ul>

<p>My algorithm is</p>

<pre><code>private static boolean bookingsPossible(ArrayList&lt;Integer&gt; arrive, ArrayList&lt;Integer&gt; depart, int K) {
        // TODO Auto-generated method stub
        int arriving_guest = 1;
        ArrayList&lt;ArrayList&lt;Integer&gt;&gt; arrange = new ArrayList&lt;ArrayList&lt;Integer&gt;&gt;();
        arrange.add(new ArrayList&lt;Integer&gt;(){{
            add(depart.get(0));
        }});
        for(int i=0;i&lt;depart.size();i++)
        {
            int temp = 0;
            System.out.println("i is "+i);
            while(temp &lt;= i)
            {
                System.out.println("arriving guest "+arriving_guest);
                if(arriving_guest &lt; arrive.size() &amp;&amp; arriving_guest &lt; depart.size())
                {
                    System.out.println("i is in if "+i);
                    if(temp &lt;= (arrange.size() -1))
                    {
                    System.out.println("Temp is "+temp);
                    int vacatetime = arrange.get(temp).get(arrange.get(temp).size() - 1);
                    System.out.println("Vacate Time "+vacatetime+" Arrival Time "+arrive.get(arriving_guest));
                    if(vacatetime &lt;= arrive.get(arriving_guest))
                    {
                        arrange.get(temp).add(depart.get(arriving_guest));
                        arriving_guest++;
                        System.out.println("Arrangement made "+arrange.toString());
                        break;
                    }
                    }
                    else
                    {
                        System.out.println("Adding room");
                        ArrayList&lt;Integer&gt; p = new ArrayList&lt;Integer&gt;();
                        p.add(depart.get(arriving_guest));
                        arrange.add(p);
                        System.out.println("Arrangement made "+arrange.toString());
                        arriving_guest++; break;
                    }

                }
                else
                {
                    break;
                }
                temp++;
            }
        }
        System.out.println("Rooms needed "+arrange.size());
        System.out.println("Final Arrangement made "+arrange.toString());
        return arrange.size() &lt;= K ? true : false;
    }
</code></pre>