1

Как определить пересечение графиков работы клиентов? Например, если первый клиент работает с 7 до 15, а второй с 6 до 10, то пересечением будет являться график с 7 до 10.

var time_1 = [7, 6];
var time_2 = [15, 10];
function getArray(array_1, array_2){
  var new_array = [];
  for(var i = 0; i < array_1.length; i++){
    for(var j = 0; j < array_2[i] - array_1[i] + 1; j++){
      if(j == 0){
        new_array.push([array_1[i]]);
      } else {
        new_array[i][j] = new_array[i][j - 1] + 1;
      }
    }
  }
  return new_array;
}
function intersection(array_1, array_2){
  var result = [];
  for(var i = 0; i < array_1.length; i++){
    for(var j = 0; j < array_2.length; j++){
      if(array_1[i] == array_2[j]){
        result.push(array_2[j]);
      }
    }
  }
  return result;
}

alert('Пересечение: ' + intersection(getArray(time_1, time_2)[0], getArray(time_1, time_2)[1]).join(', '));
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Массив time_1 - время начала работы клиентов, массив time_2 - время окончания работы клиентов.

Проблема в том, что реализована возможность попарного сравнения массивов, но если, например, клиентов будет больше 3-х, и к тому же графики не пересекаются, то возникает загвоздка в реализации.

2
  • Что должно быть результатом для большего количества клиентов?
    – MBo
    28 мая 2018 в 10:08
  • Для большого количества клиентов должен быть диапазон времени, в который данных клиентов надо обслужить, и при этом успеть к каждому, но если диапазоны не пересекаются, то вывести такие диапазоны. Например, графики работы 9-18, 5-10, 7-11, 12-23 можно "схлопнуть" до двух диапазонов - 9-10 и 12-23, т.е. если 4 клиента имеют такой график работы, то обслужить первых трех можно с 9-10, а с 12-23 - четвертого клиента.
    – Roman69
    28 мая 2018 в 12:27

2 ответа 2

1

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

Первая часть решается созданием массива, содержащего тупли (время, признак+1/-1 для начала или конца интервала клиента, номер клиента), сортировке его по времени (признак как вторичный ключ, если время совпадает - сначала -1), и обход полученного массива по порядку с суммированием признаков.

 9-18, 5-10, 7-11, 12-23
 организуем массив или список
 (9,1,0), (18,-1,0), (5,1,1),(10,-1,1),(7,1,2),(11,-1,2),(12,1,3),(23,-1,3)
 сортируем
   (5,1,1),(7,1,2),(9,1,0),(10,-1,1),(11,-1,2),(12,1,3),(18,-1,0),(23,-1,3)
 обходим, текущая сумма (количество активных клиентов)
 0    1       2       3        2          1        2         1         0
 подинтервалы
       a(5-7)   b(7-9)  c(9-10)   d(10-11)  e(11-12)  f(12-18)   g(18-23)
 клиенты
         1      1,2    0,1,2       0,2          0          0,3       3 
 списки смежности графа
 0:  c,d,e,f
 1:  a,b,c
 2:  b,c,d
 3:  f,g
 покрытие левой доли - b,f или c,f или c,g

Когда сумма обнуляется, начинается пустой промежуток, иначе заканчивается предыдущий интервал и начинается новый. Каждый из новых подинтервалов связан с активными клиентами - таким образом получается двудольный граф.

Для этого графа решается, если я не ошибаюсь, задача о минимальном количеств исполнителей - она эквивалентна нахождению покрытия множества и NP-hard, так что гарантированно её можно решить лишь полным перебором.

2
  • В теории звучит не особо понятно, а как это реализовать и подавно)
    – Roman69
    28 мая 2018 в 13:25
  • Показал на примере из вопроса.
    – MBo
    28 мая 2018 в 13:53
0

Решил вопрос следующим образом:

function compare_time_interval(a, b) {
  var a1 = Number(a.split('-')[0]);
  var a2 = Number(a.split('-')[1]);
  var b1 = Number(b.split('-')[0]);
  var b2 = Number(b.split('-')[1]);
  if (a1 < b1) {
    return -1;
  } else {
    if (a1 > b1) {
      return 1;
    } else {
      if (a2 < b2) {
        return -1;
      } else {
        if (a2 > b2) {
          return 1;
        } else {
          return 0;
        }
      }
    }
  }
}

function findElement(array, element) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] == element) {
      return i;
    }
  }
  return null;
}

function deleteElement(array, index) {
  var result = [];
  for (var i = 0; i < array.length; i++) {
    if (i != index) {
      result.push(array[i]);
    }
  }
  return result;
}

function IntersecArrays(A, B) {
  var m = A.length,
    n = B.length,
    c = 0,
    C = [];
  for (var i = 0; i < m; i++) {
    var j = 0,
      k = 0;
    while (B[j] !== A[i] && j < n) {
      j++;
    }
    while (C[k] !== A[i] && k < c) {
      k++;
    }
    if (j != n && k == c) {
      C[c++] = A[i];
    }
  }
  return C;
}

function MultiIntersecArrays(k, A) {
  var n = A.length;
  if (k == n - 2) {
    return IntersecArrays(A[n - 2], A[n - 1]);
  } else {
    return IntersecArrays(A[k], MultiIntersecArrays(k + 1, A));
  }
}

function isEmpty(array) {
  if (array.length == 0) {
    return true;
  }
  for (var i = 0; i < array.length; i++) {
    if (array[i].length == 0) {
      return true;
    }
  }
  return false;
}

function generateTimeArray(time_1, time_2) {
  var time_array = [];
  for (var i = 0; i < time_1.length; i++) {
    if (time_1[i] != 'Нет') {
      var tmp = [];
      for (var j = time_1[i]; j <= time_2[i]; j++) {
        tmp.push(j);
      }
      time_array.push(tmp);
    }
  }
  return time_array;
}

function compareTimeInterval(time_array) {
  var res_time_array = [];
  var index_array = [];
  for (var i = 0; i < time_array.length; i++) {
    index_array.push(0);
  }
  while (findElement(index_array, 0) != null) {
    for (var i = 0; i < index_array.length; i++) {
      var index = 0;
      var index_value = [];
      if (index_array[i] == 0) {
        index = i;
        index_value = time_array[i];
        break;
      }
    }
    if (isEmpty(res_time_array)) {
      res_time_array.push(index_value);
      index_array[index] = 1;
    } else {
      res_time_array.push(index_value);
      var tmp = MultiIntersecArrays(0, res_time_array);
      if (tmp.length != 0) {
        res_time_array = [tmp];
        index_array[index] = 1;
      } else {
        res_time_array = deleteElement(res_time_array, res_time_array.length - 1);
        index_array[index] = 2;
      }
    }
  }
  return {
    res_time_array,
    index_array
  };
}

function getTimeInterval(time_1, time_2) {
  var time_array = generateTimeArray(time_1, time_2);
  var res_time_array = [];
  if (time_array.length <= 1) {
    res_time_array = time_array;
  } else {
    var k = time_array.length; // кол-во необраб. элементов на прошлом шаге
    var n = time_array.length - 1; // кол-во необраб. элементов на текущем шаге
    var new_time_array = time_array;
    while (k >= n && new_time_array.length) {
      res_time_array.push(compareTimeInterval(new_time_array).res_time_array);
      var index_tmp = compareTimeInterval(new_time_array).index_array;
      k = n;
      n = 0;
      var tmp = new_time_array;
      new_time_array = [];
      for (var i = 0; i < index_tmp.length; i++) {
        if (index_tmp[i] == 2) {
          n++;
          new_time_array.push(tmp[i]);
        }
      }
    }
  }
  var time_interval_array = [];
  for (var i = 0; i < res_time_array.length; i++) {
    for (var j = 0; j < res_time_array[i].length; j++) {
      if (res_time_array[i][j].length == 1) {
        time_interval_array.push((res_time_array[i][j][0] - 1) + '-' + (res_time_array[i][j][res_time_array[i][j].length - 1] + 1));
      } else {
        time_interval_array.push(res_time_array[i][j][0] + '-' + res_time_array[i][j][res_time_array[i][j].length - 1]);
      }
    }
  }
  return time_interval_array.sort(compare_time_interval);
}

$(document).ready(function() {
  // времена работы 9-18, 5-10, 7-11, 12-23
  var time_1 = [9, 5, 7, 12];
  var time_2 = [18, 10, 11, 23];
  alert('Время обслуживания клиентов: ' + getTimeInterval(time_1, time_2).join(', '));
});
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.