# Return the optimal time slot

Implement a function meetingPlanner that given the availability, slotsA and slotsB, of two people and a meeting duration dur, returns the earliest time slot that works for both of them and is of duration dur. If there is no common time slot that satisfies the duration requirement, return null.

Examples:

input:  slotsA = [[10, 50], [60, 120], [140, 210]]
slotsB = [[0, 15], [60, 70]]
dur = 8
output: [60, 68]

input:  slotsA = [[10, 50], [60, 120], [140, 210]]
slotsB = [[0, 15], [60, 70]]
dur = 12
output: null # since there is no common slot whose duration is 12


This is my approach to the solution:

    import java.io.*;
import java.util.*;
import java.lang.*;

class Solution {

static int[] meetingPlanner(int[][] slotsA, int[][] slotsB, int dur) {
int i = 0,j = 0;
int maxStartDur,minEndDur, overlap;
int [] optTime = new int[2];
int [] nullArr = new int[0];
for( i = 0; i < slotsA.length; i++)
{
for(j = 0; j < slotsB.length; j++ )
{
//Calculate the overlap between corresponding times
maxStartDur = Math.max(slotsA[i][0],slotsB[j][0]);
minEndDur = Math.min(slotsA[i][1], slotsB[j][1]);
overlap = minEndDur - maxStartDur;

if( overlap >= dur )
{
optTime[0] = maxStartDur;
optTime[1] = maxStartDur + dur;
return optTime;
}
/* minDur = Math.min((slotsA[i][1] - slotsA[i][0]),(slotsB[j][1] - slotsB[j][0]));
if( minDur >= dur)
{
optTime[0] = slotsA[i][0];
optTime[1] = slotsA[i][0] + dur;
}
else
break;
}
*/
}

}

return nullArr;
}
// Time complexity:  O(slotsA.length*slotsB.length)
//Space complexity: O(array of size [2])
public static void main(String[] args) {

}

}


These are some of the questions regarding this code:

1. Can I further optimize this code to have an improved time and space complexity?

2. Is there a smarter approach to solve this question?

3. Are there better data structures available which I can use to solve this question more appropriately?

Reference

Yes, code can be optimized to O(slotsA.length + slotsB.length) asumming that slotsA and slotsB are already sorted and the time ranges in each input do not overlap (which seems to be the case from your example).

Haven´t tested code and there are probably some edge cases missing but it should give you the idea:

    int idxA, idxB = 0;
int maxStartDur, minEndDur, overlap;

while (idxA < slotsA.length && idxB < slotsB.length) {
maxStartDur = Math.max(slotsA[idxA][0],slotsB[idxB][0]);
minEndDur = Math.min(slotsA[idxA][1], slotsB[idxB][1]);
overlap =  minEndDur - maxStartDur;

if( overlap >= dur ) {
optTime[0] = maxStartDur;
optTime[1] = maxStartDur + dur;
return optTime;
}

if (slotsA[idxA][1] > slotsB[idxB][1]) {
idxB += 1;
} else {
idxA += 1;
}

}


In your case, you start with 10-50 and 0-15. It did not give enough overlap. Is it worth comparing 0-15 with the other slotA ranges? No, because the others will start at more than 50, and they won´t overlap.

Is it worth comparing 10-50 with other slotB ranges? Yes, because there could be a 20-30 range afterwards. Basically, 50 is greater than 15, so thats our hint that we can keep growing that 15 going to next range from slotB and as long as its less than 50, we might keep having an overlap.

If you keep doing this, you will arrive at desired answer.

There might be data structures suited for this, but its still simple enough to not need one.

• you will get an index out of bounds exception. Update the while condition while (idxA < slotsA.length && idxB < slotsB.length) – nayakam Sep 9 '18 at 14:15