Подсчитать количество встречных чисел

Question

У меня есть набор событий для календаря. Это будет помещено в сетку.

Я пытаюсь подсчитать наибольшее количество событий, которые сталкиваются одновременно. Каждое событие имеет время start и end.

То, что я до сих пор делал, - это подсчитываю количество совпадений, но это не определяет максимальное количество столкновений.

const events = [{
    id: 0,
    start: 6,
    end: 9,
    title: "Hello"
  },
  {
    id: 1,
    start: 6,
    end: 9,
    title: "Hello"
  },
  {
    id: 2,
    start: 7,
    end: 8,
    title: "Hello"
  },
  {
    id: 3,
    start: 10,
    end: 15,
    title: "Hello"
  },
  {
    id: 4,
    start: 20,
    end: 25,
    title: "Hello"
  },
  {
    id: 5,
    start: 21,
    end: 23,
    title: "Hello"
  },
]

// Check how many events are colliding at same time, to make more columns
let items = []
events.map(event => {
  const matches = events.filter(o => {
    //console.log(o.start, "is smaller or same", event.start, o.start <= event.end)
    return o.start <= event.end && o.end >= event.start && event.id !== o.id
  })
  items.push({
    ...event,
    matches
  })
})

const collitions = items.sort((a, b) => {
  if (a.matches < b.matches) return 1
  if (a.matches > b.matches) return -1
  return 0
})[0].matches.length + 1

console.log('There is', collitions, 'collitions')

Вот таблица, в которой в примере используются данные о событиях. Он выводит три, что правильно.

Вот таблица, когда происходит событие, которое является целым днем. Он выводит 6 встречных событий, но это неправильно. Это 4 встречных события подряд.

Answer 1

Вот более простое решение.

Подход

• Имеет массив длиной 24, чтобы каждое значение представляло 1 час
• L oop через каждое событие и увеличивайте значение в каждый час на время
• . В конце найдите максимальное значение в массиве

Код

const events = [{
    id: 0,
    start: 6,
    end: 9,
    title: "Hello"
  },
  {
    id: 1,
    start: 6,
    end: 9,
    title: "Hello"
  },
  {
    id: 2,
    start: 7,
    end: 8,
    title: "Hello"
  },
  {
    id: 3,
    start: 10,
    end: 15,
    title: "Hello"
  },
  {
    id: 4,
    start: 20,
    end: 25,
    title: "Hello"
  },
  {
    id: 5,
    start: 21,
    end: 23,
    title: "Hello"
  },
]

const array = new Array(24).fill(0)
events.forEach(function(event) {
  for (let i = event.start; i < event.end; ++i) {
    ++array[i]
  }
})

let maxEvents = -1
for (let i = 0; i< array.length; ++i) {
  if (array[i] > maxEvents) maxEvents = array[i]
}

console.log("collisions: ", maxEvents)
console.log("collision array:", JSON.stringify(array))

Проверили это для случая, когда event.start = 0 и event.end = 23, и он дает правильный вывод

Примечание:

Решение также будет работать в случае, если время начала и окончания hm:mm. В этом случае нам нужен массив длиной 24*60 (hours*mins). Кроме того, i внутри для l oop будет общим количеством минут, начиная с 0 (например, 2:45 mean i = 165).

Надеюсь, это поможет. Возврат для любых сомнений.

Answer 2

Можно использовать другой подход, используя массив слотов.

Сначала сортируйте данные по возрастанию start и уменьшению (почему? Просто чтобы сначала получить более длинные детали) end, чтобы получить более крупные события first.

Затем уменьшите данные и посмотрите в массив для последнего события и проверьте конец этого события с началом фактического события. Если оба совпадают, возьмите этот слот, в противном случае добавьте событие в новый массив слотов.

В результате получается массив массивов с неконтролирующими четными числами. Чтобы получить число максимальных столкновений, вы можете просто взять длину slots.

var events = [{ id: 0, start: 6, end: 9, title: "Hello" }, { id: 1, start: 6, end: 9, title: "Hello" }, { id: 2, start: 7, end: 8, title: "Hello" }, { id: 3, start: 10, end: 15, title: "Hello" }, { id: 4, start: 20, end: 25, title: "Hello" }, { id: 5, start: 21, end: 23, title: "Hello" }, { id: 6, start: 0, end: 24, title: "Hello" }],
    slots = events.sort((a, b) => a.start - b.start || b.end - a.end)
        .reduce((r, event) => {
            var slot = r.find(a => a[a.length - 1].end <= event.start);
            if (!slot) r.push(slot = []);
            slot.push(event);
            return r;
        }, []);

console.log(slots.length);
console.log(slots);

.as-console-wrapper { max-height: 100% !important; top: 0; }