Gui B.L Software Engineering-Code and posts about tech and programming

Find first K available timeslots for N people
19 March 2015
Problem overview

You are given a function: List getTimeSlots (String friend) Assume getTimeSlots() returns available times for a friend, sorted in order, with no overlap. You want to schedule a meeting among all of your friends, such that all can attend. Implement a function to get the first k common TimeSlots among all your friends:
Example:
user1 1-2pm, 3-4pm, 7-8pm user2 1-2pm, 5-6pm, 7-9pm
first 2 common: 1-2pm, 7-8pm
Algorithm analysis

pick a person as a pivot, let's say the first friend let's call him A. If there are common timeslots, then at least 1 timeslot of A in common with all others.
Iterate over A's timeslots and compare them with all others, if A's current timeslot has no match with any of the next person's timeslots, flag it as not a candidate. interrupt iteration and pick next slot of A.
If A's current timeslot matches (or intersects) all others include it as part of the final result. Keep them in a Hashset to avoid duplicates. Do this until there's no more timeslots for A or if you already found K target timeslots.
Obs: using time as int range from 0 - 23, so 1PM will be 13, while 1AM will be 1. This is to facilitate timeslot calculation. Solution: Time: O(m(log(n)) - where m is the number of slots of Person chosen as pivot, memory: O(1).
Code in Java

public class Solution {

<span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">List</span><span class="o">&lt;</span><span class="n">List</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;&gt;</span> <span class="n">timeslots</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ArrayList</span><span class="o">&lt;</span><span class="n">List</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;&gt;();</span>

    <span class="c1">// friend 1</span>
    <span class="n">List</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;</span> <span class="n">timeSlotList</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ArrayList</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;();</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">6</span><span class="o">,</span> <span class="mi">9</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">10</span><span class="o">,</span> <span class="mi">14</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">16</span><span class="o">,</span> <span class="mi">17</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">19</span><span class="o">,</span> <span class="mi">20</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">21</span><span class="o">,</span> <span class="mi">22</span><span class="o">));</span>
    <span class="n">timeslots</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">timeSlotList</span><span class="o">);</span>

    <span class="c1">// friend 2</span>
    <span class="n">timeSlotList</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ArrayList</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;();</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">7</span><span class="o">,</span> <span class="mi">8</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">13</span><span class="o">,</span> <span class="mi">14</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">17</span><span class="o">,</span> <span class="mi">18</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">20</span><span class="o">,</span> <span class="mi">23</span><span class="o">));</span>
    <span class="n">timeslots</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">timeSlotList</span><span class="o">);</span>

    <span class="c1">// friend 3</span>
    <span class="n">timeSlotList</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ArrayList</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;();</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">5</span><span class="o">,</span> <span class="mi">8</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">13</span><span class="o">,</span> <span class="mi">15</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">19</span><span class="o">,</span> <span class="mi">20</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">21</span><span class="o">,</span> <span class="mi">23</span><span class="o">));</span>
    <span class="n">timeslots</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">timeSlotList</span><span class="o">);</span>

    <span class="c1">// friend 4</span>
    <span class="n">timeSlotList</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ArrayList</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;();</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">6</span><span class="o">,</span> <span class="mi">8</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">13</span><span class="o">,</span> <span class="mi">16</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">19</span><span class="o">,</span> <span class="mi">20</span><span class="o">));</span>
    <span class="n">timeSlotList</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="mi">21</span><span class="o">,</span> <span class="mi">22</span><span class="o">));</span>
    <span class="n">timeslots</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">timeSlotList</span><span class="o">);</span>

    <span class="n">printFirstNCommonTimeslots</span><span class="o">(</span><span class="n">timeslots</span><span class="o">,</span> <span class="mi">3</span><span class="o">);</span>
<span class="o">}</span>

<span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">printFirstNCommonTimeslots</span><span class="o">(</span><span class="n">List</span><span class="o">&lt;</span><span class="n">List</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;&gt;</span> <span class="n">timeslots</span><span class="o">,</span> <span class="kt">int</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">n</span> <span class="o">&lt;=</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">timeslots</span> <span class="o">==</span> <span class="kc">null</span> <span class="o">||</span> <span class="n">timeslots</span><span class="o">.</span><span class="na">isEmpty</span><span class="o">())</span> <span class="o">{</span>
        <span class="k">return</span><span class="o">;</span>           
    <span class="o">}</span>        
    <span class="n">Set</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;</span> <span class="n">commonTimeSlots</span> <span class="o">=</span> <span class="k">new</span> <span class="n">HashSet</span><span class="o">&lt;&gt;();</span>

    <span class="n">TimeSlot</span> <span class="n">candidate</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">candidatesFound</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">listsAnalyzed</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="kt">boolean</span> <span class="n">stillCandidate</span> <span class="o">=</span> <span class="kc">false</span><span class="o">;</span>
    <span class="kt">boolean</span> <span class="n">candidateFound</span> <span class="o">=</span> <span class="kc">false</span><span class="o">;</span>

    <span class="c1">// get timeslots from first person and check if it matches with all others</span>
    <span class="n">List</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;</span> <span class="n">firstPersonTimeslots</span> <span class="o">=</span> <span class="n">timeslots</span><span class="o">.</span><span class="na">get</span><span class="o">(</span><span class="mi">0</span><span class="o">);</span>             
    <span class="k">for</span> <span class="o">(</span><span class="n">TimeSlot</span> <span class="n">timeSlot</span> <span class="o">:</span> <span class="n">firstPersonTimeslots</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">candidate</span> <span class="o">=</span> <span class="n">timeSlot</span><span class="o">;</span>
        <span class="n">stillCandidate</span> <span class="o">=</span> <span class="kc">true</span><span class="o">;</span>         
        <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span>
        <span class="k">while</span><span class="o">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">timeslots</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">&amp;&amp;</span> <span class="n">stillCandidate</span><span class="o">)</span> <span class="o">{</span>
            <span class="n">List</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;</span> <span class="n">listT</span> <span class="o">=</span> <span class="n">timeslots</span><span class="o">.</span><span class="na">get</span><span class="o">(</span><span class="n">i</span><span class="o">);</span>

            <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">listT</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">candidateFound</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
                <span class="n">TimeSlot</span> <span class="n">timeSlot2</span> <span class="o">=</span> <span class="n">listT</span><span class="o">.</span><span class="na">get</span><span class="o">(</span><span class="n">j</span><span class="o">);</span>

                <span class="kt">int</span> <span class="n">initTimeA</span> <span class="o">=</span> <span class="n">candidate</span><span class="o">.</span><span class="na">init</span><span class="o">;</span>
                <span class="kt">int</span> <span class="n">endTimeA</span> <span class="o">=</span> <span class="n">candidate</span><span class="o">.</span><span class="na">end</span><span class="o">;</span>
                <span class="kt">int</span> <span class="n">initTimeB</span> <span class="o">=</span> <span class="n">timeSlot2</span><span class="o">.</span><span class="na">init</span><span class="o">;</span>                                      
                <span class="kt">int</span> <span class="n">endTimeB</span> <span class="o">=</span> <span class="n">timeSlot2</span><span class="o">.</span><span class="na">end</span><span class="o">;</span>

                <span class="k">if</span> <span class="o">(</span><span class="n">initTimeA</span> <span class="o">==</span> <span class="n">initTimeB</span> <span class="o">||</span> <span class="n">endTimeB</span> <span class="o">==</span> <span class="n">endTimeA</span> <span class="o">||</span>
                        <span class="o">(</span><span class="n">initTimeA</span> <span class="o">&lt;</span> <span class="n">endTimeB</span> <span class="o">&amp;&amp;</span> <span class="n">initTimeA</span> <span class="o">&gt;</span> <span class="n">initTimeB</span><span class="o">)</span> <span class="o">||</span>
                        <span class="o">(</span><span class="n">initTimeB</span> <span class="o">&lt;</span> <span class="n">endTimeA</span> <span class="o">&amp;&amp;</span> <span class="n">initTimeB</span> <span class="o">&gt;</span> <span class="n">initTimeA</span><span class="o">))</span> <span class="o">{</span>

                    <span class="k">while</span> <span class="o">(</span><span class="n">initTimeA</span> <span class="o">!=</span> <span class="n">initTimeB</span><span class="o">)</span> <span class="o">{</span>
                        <span class="k">if</span> <span class="o">(</span><span class="n">initTimeA</span> <span class="o">&lt;</span> <span class="n">initTimeB</span><span class="o">)</span> <span class="o">{</span>
                            <span class="n">initTimeA</span><span class="o">++;</span>
                        <span class="o">}</span> <span class="k">else</span> <span class="k">if</span> <span class="o">(</span><span class="n">initTimeA</span> <span class="o">&gt;</span> <span class="n">initTimeB</span><span class="o">)</span> <span class="o">{</span> 
                            <span class="n">initTimeB</span><span class="o">++;</span>
                        <span class="o">}</span>
                    <span class="o">}</span>

                    <span class="k">while</span> <span class="o">(</span><span class="n">endTimeA</span> <span class="o">!=</span> <span class="n">endTimeB</span><span class="o">)</span> <span class="o">{</span>
                        <span class="k">if</span> <span class="o">(</span><span class="n">endTimeA</span> <span class="o">&lt;</span> <span class="n">endTimeB</span><span class="o">)</span> <span class="o">{</span>
                            <span class="n">endTimeB</span><span class="o">--;</span>
                        <span class="o">}</span> <span class="k">else</span> <span class="k">if</span> <span class="o">(</span><span class="n">endTimeA</span> <span class="o">&gt;</span> <span class="n">endTimeB</span><span class="o">)</span> <span class="o">{</span>
                            <span class="n">endTimeA</span><span class="o">--;</span>                               
                        <span class="o">}</span>                        
                    <span class="o">}</span>

                    <span class="n">candidate</span> <span class="o">=</span> <span class="k">new</span> <span class="n">TimeSlot</span><span class="o">(</span><span class="n">initTimeA</span><span class="o">,</span> <span class="n">endTimeA</span><span class="o">);</span>
                    <span class="n">candidateFound</span> <span class="o">=</span> <span class="kc">true</span><span class="o">;</span>                     
                <span class="o">}</span>                                                                                            
            <span class="o">}</span>

            <span class="k">if</span> <span class="o">(</span><span class="n">candidateFound</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">listsAnalyzed</span><span class="o">++;</span>
                <span class="n">candidateFound</span> <span class="o">=</span> <span class="kc">false</span><span class="o">;</span>
            <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
                <span class="n">stillCandidate</span> <span class="o">=</span> <span class="kc">false</span><span class="o">;</span>
                <span class="n">listsAnalyzed</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>                 
            <span class="o">}</span>

            <span class="n">i</span><span class="o">++;</span>
        <span class="o">}</span>


        <span class="k">if</span> <span class="o">(</span><span class="n">listsAnalyzed</span> <span class="o">==</span> <span class="n">timeslots</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">-</span> <span class="mi">1</span><span class="o">)</span> <span class="o">{</span>
            <span class="n">commonTimeSlots</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">candidate</span><span class="o">);</span>              
            <span class="n">candidatesFound</span><span class="o">++;</span>
            <span class="n">listsAnalyzed</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>

            <span class="k">if</span> <span class="o">(</span><span class="n">candidatesFound</span> <span class="o">==</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
                <span class="k">break</span><span class="o">;</span>
            <span class="o">}</span>
        <span class="o">}</span>
    <span class="o">}</span>        


    <span class="k">if</span> <span class="o">(</span><span class="n">candidatesFound</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Iterator</span><span class="o">&lt;</span><span class="n">TimeSlot</span><span class="o">&gt;</span> <span class="n">timeSlots</span> <span class="o">=</span> <span class="n">commonTimeSlots</span><span class="o">.</span><span class="na">iterator</span><span class="o">();</span>         
        <span class="k">while</span><span class="o">(</span><span class="n">timeSlots</span><span class="o">.</span><span class="na">hasNext</span><span class="o">())</span> <span class="o">{</span>              
            <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">timeSlots</span><span class="o">.</span><span class="na">next</span><span class="o">());</span>
        <span class="o">}</span>            
    <span class="o">}</span>
<span class="o">}</span>


}

class TimeSlot {
    int init;
    int end;

<span class="kd">public</span> <span class="nf">TimeSlot</span><span class="o">(</span><span class="kt">int</span> <span class="n">init</span><span class="o">,</span> <span class="kt">int</span> <span class="n">end</span><span class="o">)</span> <span class="o">{</span>
    <span class="kd">super</span><span class="o">();</span>
    <span class="k">this</span><span class="o">.</span><span class="na">init</span> <span class="o">=</span> <span class="n">init</span><span class="o">;</span>
    <span class="k">this</span><span class="o">.</span><span class="na">end</span> <span class="o">=</span> <span class="n">end</span><span class="o">;</span>
<span class="o">}</span>

<span class="nd">@Override</span>
<span class="kd">public</span> <span class="n">String</span> <span class="nf">toString</span><span class="o">()</span> <span class="o">{</span>
    <span class="k">return</span> <span class="n">init</span> <span class="o">+</span> <span class="s">" "</span> <span class="o">+</span> <span class="n">end</span><span class="o">;</span>       
<span class="o">}</span>

<span class="nd">@Override</span>
<span class="kd">public</span> <span class="kt">boolean</span> <span class="nf">equals</span><span class="o">(</span><span class="n">Object</span> <span class="n">obj</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">if</span> <span class="o">(</span><span class="k">this</span> <span class="o">==</span> <span class="n">obj</span><span class="o">)</span>
        <span class="k">return</span> <span class="kc">true</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">obj</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
        <span class="k">return</span> <span class="kc">false</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">getClass</span><span class="o">()</span> <span class="o">!=</span> <span class="n">obj</span><span class="o">.</span><span class="na">getClass</span><span class="o">())</span>
        <span class="k">return</span> <span class="kc">false</span><span class="o">;</span>
    <span class="n">TimeSlot</span> <span class="n">other</span> <span class="o">=</span> <span class="o">(</span><span class="n">TimeSlot</span><span class="o">)</span> <span class="n">obj</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">end</span> <span class="o">!=</span> <span class="n">other</span><span class="o">.</span><span class="na">end</span><span class="o">)</span>
        <span class="k">return</span> <span class="kc">false</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">init</span> <span class="o">!=</span> <span class="n">other</span><span class="o">.</span><span class="na">init</span><span class="o">)</span>
        <span class="k">return</span> <span class="kc">false</span><span class="o">;</span>
    <span class="k">return</span> <span class="kc">true</span><span class="o">;</span>
<span class="o">}</span>


}
Full source code