2
\$\begingroup\$

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) {
        // your code goes here
        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

\$\endgroup\$
4
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.