Вернуть оптимальное время


Реализовать функцию meetingPlanner , что при наличии, slotsA и slotsB, двух человек и конференц-продолжительность дур, возвращает ближайшее время, что работает для них обоих и продолжительности дур. Если нет общей временной интервал, который удовлетворяет продолжительность требованием, возвратить нуль.

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

Это мой подход к решению:

    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) {

      }

    }

Таковы некоторые вопросы, касающиеся этого кода:

  1. Я могу оптимизировать этот код, чтобы улучшить время и сложность пространства?

  2. Есть разумный подход, чтобы решить этот вопрос?

  3. Там лучше существующих структур данных, которые я могу использовать, чтобы более правильно решить этот вопрос?

Ссылка



Комментарии
1 ответ

Да, код можно оптимизировать до o(slotsA.длина + slotsB.длина) asumming, что slotsA и slotsB уже отсортированы и колеблется на каждом входе не пересекаются (что представляется случай из вашего примера).

Не проверенный код и есть, вероятно, некоторые недостающие граничные случаи, но она должна дать вам идею:

    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;
}

}

В вашем случае, вы начинаете с 10-50 и 0-15. Он не дал достаточно пересекаются. Стоит ли сравнивать 0-15 с другими диапазонами слота? Нет, потому что другие начнут в более чем 50, и они не пересекаются.

Стоит ли сравнивать 10-50 с другими диапазонами slotB? Да потому, что там может быть в диапазоне 20-30 после. В принципе, 50 больше, чем 15, так вот наш намек на то, что мы можем продолжать расти, что 15 будет в следующем диапазоне от slotB и пока ее меньше, чем 50, мы могли бы держать совпадении.

Если вы продолжаете делать это, вы попадете в нужный ответ.

Там может быть структур данных подходят для этого, но его все еще достаточно просто не нужен.

4
ответ дан 19 февраля 2018 в 08:02 Источник Поделиться