Проверьте, назначен ли пользователь определенному слоту

Question

Я работаю над приложением по подбору персонала.У нас есть возможность переводить сотрудников в команды.Я хочу добавить проверку, чтобы проверить, если пользователь уже забронировал на этот конкретный период.Например, на скриншоте ниже слот пользователя mate перекрывается.Его нельзя назначить двум командам за один и тот же период времени.

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

Ничего страшного, если нам нужно изменить структуру данных для повышения производительности.

Answer 1

Эта демонстрация имеет class с несколькими методами, которые используют ES6 Map для хранения диапазонов дат.Каждая инструкция представляет график сотрудника.В OP не упоминалось, что делать с перекрывающимися датами, поэтому вот правила проверки диапазона дат:

• Даты для сравнения преобразуются в миллисекунды (.getTime())

• Если начальная дата больше другой начальной даты и меньше ее конечной даты, то используется самая ранняя начальная дата, и тогда новая конечная дата будет больше двух из двух конечных дат.

• Если дата начала ввода больше даты окончания ввода, они меняются местами.

• Каждый диапазон сохраняется индексом.

Кстати, даты точные, но формат меняется, я оставлю это доОП.

class schedule {
  constructor(id) {
    this.id = id;
    this.index = 0;
    this.map = new Map;
  }
  addSlot([startString, endString]) {
    this.index = this.map.size;
    let startDate = new Date(startString);
    let endDate = new Date(endString);
    let startTime = startDate.getTime();
    let endTime = endDate.getTime()
    if (startTime > endTime) {
      let temp = endDate;
      endDate = startDate;
      startDate = temp;
    }
    if (this.map.size > 0) {
      for (let [key, value] of this.map) {
        let start = value[0].getTime();
        let end = value[1].getTime();
        let newStart = startTime > start && startTime < end ? value[0] : start > startTime && start < endTime ? startDate : false;
        let newEnd;
        if (newStart) {
          newEnd = end > endTime ? value[1] : endDate;
          this.map.set(key, [newStart, newEnd]);
        } else {
          this.map.set(this.index, [startDate, endDate]);
        }
      }
    } else {
      this.map.set(this.index, [startDate, endDate]);
    }
  }

  hasSlot(index) {
    return this.map.has(index);
  }

  getSlot(index) {
    return this.map.get(index);
  }

  viewSlots() {
    let list = '';
    for (let [key, value] of this.map) {
      list += `
      ${key}: [Start: ${value[0]} - 
          End: ${value[1]}]
      `;
    }
    return list;
  }

  removeSlot(index) {
    if (this.map.has(index)) {
      this.map.delete(index);
    } else {
      return index + 'does not exist';
    }
  }
}

const m = new schedule('Mate');

console.log(m.id);

m.addSlot(['04/19/2019', '04/28/2019']);
console.log(m.hasSlot(0));

m.addSlot(['04/21/2019', '05/12/2019']);
console.log(m.hasSlot(1));
console.log(m.getSlot(0));

m.addSlot(['08/19/2019', '09/12/2019']);
console.log(m.hasSlot(1));
console.log(m.getSlot(1));

console.log(m.viewSlots());

Answer 2

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

Поскольку вас интересуют неперекрывающиеся интервалы, для них определен естественный порядок: интервал A> интервал B, если A лежит справа от B на оси времени.

Вы можете добавлять интервалы один за другим, проверяя в то же время, что каждый новый интервал не перекрывается с существующими. Для каждого нового интервала потребуется O (log n). Если интервал редактируется, то вы должны удалить соответствующий узел и добавить новый, сохраняя структуру двоичного дерева, конечно.

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