Создание оптимального выбора перекрывающихся временных интервалов

Question

Автосалон сдает в аренду редкий Aston Martin DBR1 1956 года выпуска (из которого Aston Martin только когда-либо делал 5). Поскольку существует так много запросов на аренду, дилер решает разместить заказы на весь год вперед. Он собирает запросы и теперь должен выяснить, какие запросы следует принять.

Создайте сценарий, который выбирает запросы на аренду таким образом, чтобы наибольшее количество отдельных клиентов могли ездить в редком Астон-Мартине. Входные данные сценария представляют собой матрицу дней года, каждая строка представляет начальный и конечный дни запроса. На выходе должны быть индексы клиентов и их дневные диапазоны. Рекомендуется сначала спланировать свой код и написать свои собственные функции. В верхней части скрипта добавьте блок комментария с описанием того, как работает ваш код.

Пример списка с этими временными интервалами: list = [10 20; 9 15; 16 17; 21 100;];

(Также следуетработать для списка с 100 временными интервалами)

Мы могли бы выбрать клиентов 1 и 4, но тогда 2 и 3 невозможны, что привело бы к двум счастливым клиентам. В качестве альтернативы мы могли бы выбрать запросы 2, 3 и 4. Следовательно, три счастливых клиента являются оптимальными здесь.

Результат будет: клиенты = [2, 3, 4], дни = [9, 15; 16, 17; 21, 100]

Все IМожно подумать, проверяет, пересекаются ли интервалы, но я понятия не имею, как сделать общий оптимальный выбор.

Answer 1

Моя идея: 1) Сортировать их по дате начала

2) Сделать массив пересечений для каждого

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

4) Повторяйте точку 3, пока не останутся только единицы с пустыми массивами

В вашем примере мы получим данные

10 20 [9 15, 16 17] 
9 15 [10 20]
16 17 [10 20]
21 100 []

, такмы отклоняем 10 20, поскольку он имеет 2 пересечения, поэтому у нас будут только элементы с пустыми массивами

9 15 []
16 17 []
21 100 []

, поэтому поиск завершен

код в javascript

const inputData = ' 50 74; 6 34; 147 162; 120 127; 98 127; 120 136; 53 68; 145 166; 95 106; 242 243; 222 250; 204 207; 69 79; 183 187; 198 201; 184 199; 223 245; 264 291; 100 121; 61 61; 232 247'

// convert string to array of objects
const orders = inputData.split(';')
  .map((v, index) => (
    {
      id: index,
      start: Number(v.split(' ')[1]),
      end: Number(v.split(' ')[2]),
      intersections: []
    }
  ))

// sort them by start value
orders.sort((a, b) => a.start - b.start)

// find intersection for each one and add them to intersection array
orders.forEach((item, index) => {
  for (let i = index + 1; i < orders.length; i++) {
    if (orders[i].start <= item.end) {
      item.intersections.push(orders[i])
      orders[i].intersections.push(item)
    } else {
      break
    }
  }
})

// sort by intersections count
orders.sort((a, b) => a.intersections.length - b.intersections.length)

// loop while at least one item still has intersections
while (orders[orders.length - 1].intersections.length > 0) {
  const rejected = orders.pop()
  // remove rejected item from other's intersections
  rejected.intersections.forEach(item => {
    item.intersections = item.intersections.filter(
      item => item.id !== rejected.id
    )
  })
  // sort by intersections count
  orders.sort((a, b) => a.intersections.length - b.intersections.length)
}

// sort by start value
orders.sort((a, b) => a.start - b.start)

// show result
orders.forEach(item => { console.log(item.start + ' - ' + item.end)})

Answer 2

Хотелось немного расширить / исправить на принятый ответ.

1. Вы должны начать с сортировки по дате начала.
2. Затем принять самого последнего клиента.
3. Просмотрите список по убыванию и примите все запросы, которыене пересекаются с уже принятыми.

Это оптимальное решение.