Пересечение диапазонов

212

13 июня 2018, 23:00

Как определить пересечение графиков работы клиентов? Например, если первый клиент работает с 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-х, и к тому же графики не пересекаются, то возникает загвоздка в реализации.

Answer 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, так что гарантированно её можно решить лишь полным перебором.