Шаг 1

Задача о составлении расписания в различных её формулировках является ещё одной популярной задачей из серии решаемых жадно. Давайте посмотрим на неё и решим с помощью жадности! В вашем отделе внезапно уволились два из трёх менеджеров, и все их встречи и организационные вопросы перешли к третьему. Конечно, на все встречи один менеджер попасть не может — они просто накладываются по времени друг на друга. Помогите менеджеру организовать свой календарь таким образом, чтобы попасть на максимальное количество встреч.

import {timetable} from "./logger";

const appointments = [
  {
    title: "Планирование и приоритизация задач",
    start: 10,
    end: 13,
  },
  {
    title: "Обед",
    start: 12,
    end: 13,
  },
  {
    title: "О защите от мошенников",
    start: 10,
    end: 11,
  },
  {
    title: "Об увольнении Игоря",
    start: 14,
    end: 16,
  },
  {
    title: "Встреча, которую можно было бы заменить одним письмом",
    start: 13,
    end: 15,
  },
  {
    title: "Что подарим Кексу на день рождения?",
    start: 15,
    end: 17,
  },
  {
    title: "Вопросы с поставками",
    start: 9,
    end: 11,
  },
];

function prioritize(appointments) {
  return appointments;
}

timetable(prioritize(appointments));

Шаг 2

Решение у этой задачи невероятно простое. Сначала нам нужно найти встречу, которая заканчивается раньше остальных. После того как мы её найдём, нужно найти встречу, которая начинается после первой и заканчивается также самой первой. По такому принципу составим расписание, пока есть встречи, которые в него «помещаются». Кажется, что такой алгоритм настолько прост, что должен работать не всегда. Но нет, в этом и есть прелесть жадных алгоритмов: иногда они так просты, что даже выглядят глупо.

import {timetable} from "./logger";

const appointments = [
  {
    title: "Планирование и приоритизация задач",
    start: 10,
    end: 13,
  },
  {
    title: "Обед",
    start: 12,
    end: 13,
  },
  {
    title: "Вопросы с поставками",
    start: 9,
    end: 11,
  },
  {
    title: "Об увольнении Игоря",
    start: 14,
    end: 16,
  },
  {
    title: "Встреча, которую можно было бы заменить одним письмом",
    start: 13,
    end: 15,
  },
  {
    title: "Что подарим Кексу на день рождения?",
    start: 15,
    end: 17,
  },
  {
    title: "О защите от мошенников",
    start: 10,
    end: 11,
  },
];

function prioritize(appointments) {
  const timetable = [];

  // Сохраним здесь время начала самой поздней встречи, чтобы остановить алгоритм, когда уже перейдем это время
  const {end: latestAppointment} = appointments.reduce((currentLatest, next) =>  currentLatest.end < next.end ? next : currentLatest, appointments[0]);
  // Будем хранить здесь время окончания предыдущей встречи
  let startAfter = 0;

  // пока мы ещё можем впихнуть встречу в конец
  while (startAfter < latestAppointment) {
    // Найдем встречу, которая заканчивается максимально рано после последней и вставим её в конец!
    const nextAppointments = appointments.filter(({start}) => start >= startAfter);

    const appointment = nextAppointments
      .reduce((currentShortest, next) =>  currentShortest.end > next.end ? next : currentShortest, nextAppointments[0]);

    startAfter = appointment.end;
    timetable.push(appointment);
  }

  return timetable;
}

timetable(prioritize(appointments));

File logger.js

const timetableElement = document.getElementById('results');

export function timetable(appointments) {
  for (const {title, start, end} of appointments) {
    const appt = document.createElement('li');

    appt.innerText = `${title}, с ${start} до ${end}`;

    timetableElement.appendChild(appt);
  }
}