Meeting Schedule for 2 people


  • 0
    N

    You are given the availability for 2 people, where the availability for each person is represented by a 2d array (e.g. avail[i][0] is start time and availA[i][1] is the end time for the ith availability of person A). Also, the duration of a meeting is given. Write a method to return the earliest start time for hosting the meeting between the two.
    input:
    availA: {[0,15], [25, 50]} (person A is available from 0 to 15, from 25 to 50)
    availB: {[10, 100]} (person B is available from 10 to 100)
    duration: 20

    output: 25


  • 3
    P
      public static int earliestMeetingStart(int[][] first, int[][] second, int duration) {
    
        if (first == null || second == null || first.length == 0 || second.length == 0)
          return -1;
        int[][] duroverlap = new int[Math.max(first.length, second.length)][2];
    
        int jstart = 0;
        for (int i = 0; i < second.length; i++) {
    
          for (int j = jstart; j < first.length; j++) {
            if (first[j][0] >= second[i][1]) {
              break;
            } else if (first[j][1] <= second[i][0]) {
              jstart = j + 1;
              break;
            }
            duroverlap[j][0] = Math.max(first[j][0], second[i][0]);
            duroverlap[j][1] = Math.min(first[j][1], second[i][1]);
    
          }
    
        }
    
        for (int i = 0; i < duroverlap.length; i++) {
          int dur = duroverlap[i][1] - duroverlap[i][0];
          if (dur != 0 && dur >= duration) {
            return duroverlap[i][0];
    
          }
        }
        return -1;
      }

  • 0
    M

    Interesting approach, thanks for posting your solution. I think that due to the problem doesn't specify that the availabilities are sorted we should sort them first. Another thing that could be improved is that isn't really necessary to create the "duroverlap", you can evaluate the duration immediately instead of assign the values, I will post a solution based on yours and please tell me your thoughts


  • 1
    M
    //Based on praveenlk's solution    
    public static int getEarliestStartTime(int[][] availA, int[][] availB, int duration) {
            int unavailability = -1;
            if (availA == null || availA.length == 0 || availB == null || availB.length == 0 || duration < 1) {
                return unavailability;
            }
            Comparator<int[]> availComparator = (o1, o2) -> Integer.valueOf(o1[0]).compareTo(o2[0]);
            Arrays.sort(availA, availComparator);
            Arrays.sort(availB, availComparator);
            for (int availBIdx = 0, currentA = 0; availBIdx < availB.length; availBIdx++) {
                for (int availAIdx = currentA; availAIdx < availA.length; availAIdx++) {
                    if (availA[availAIdx][0] >= availB[availBIdx][1]) {
                        break;
                    }
                    if (availA[availAIdx][1] <= availB[availBIdx][0]) {
                        currentA = availAIdx + 1;
                        break;
                    }
                    int startTime = Math.max(availA[availAIdx][0], availB[availBIdx][0]);
                    int endTime = Math.min(availA[availAIdx][1], availB[availBIdx][1]);
                    if (endTime - startTime >= duration) {
                        return startTime;
                    }
                }
            }
            return unavailability;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.