Маркировка общих участков нескольких наборов отрезков

Условие

Имеются три разных набора отрезков. Нужно определить все участки, где они пересекаются, отметить такие пересечения как отдельные новые отрезки (например, пересечение наборов green и yellow отмечаем как новый отрезок – см. exampleResult4), вырезать их из исходных наборов и вывести последовательность получившихся отрезков в диапазоне от 0 до 100.

// Мнемоники отрезков
const Task4 = () => {
    type IMnemo = "green" | "yellow" | "red"
    //Тип для отрезка - начало и конец
    interface IInterval {
        start: number,
        end: number
    }
    type ISourceIntervals = Record<IMnemo, IInterval[]>

    //Тип ответа
    interface IExpectedResult extends IInterval {
        mnemo: IMnemo[],
    }
    //Исходные отрезки
    const sourceData: ISourceIntervals = {
        green: [{ start: 0, end: 30 }, { start: 90, end: 100 }],
        yellow: [{ start: 20, end: 40 }, { start: 50, end: 70 }],
        red: [{ start: 10, end: 50 }, { start: 70, end: 90 }],
    }

    //Ожидаемый результат
    const expectedResult: IExpectedResult[] = [
        { "mnemo": ["green"], start: 0, end: 10 },
        { "mnemo": ["green", "red"], start: 10, end: 20 },
        { "mnemo": ["green", "yellow", "red"], start: 20, end: 30 },
        { "mnemo": ["yellow", "red"], start: 30, end: 40 },
        { "mnemo": ["red"], start: 40, end: 50 },
        { "mnemo": ["yellow"], start: 50, end: 70 },
        { "mnemo": ["red"], start: 70, end: 90 },
        { "mnemo": ["green"], start: 90, end: 100 },
    ]

    // Реализовать внутри этой функции оптимальным способом, перебор исходного массива
    // может быть только один! Допускается формирования дополнительных массивов/объектов
    const getResult = (sourceIntervals: ISourceIntervals): IExpectedResult[] => {
        return expectedResult
    }

    //Это выведет результат её работы справа
    return { expectedResult: expectedResult, result: getResult(sourceData) }
}

//Вспомогательные функции
const showTaskResult =(task: number, taskResult: {result: any, expectedResult: any}) => {
    console.log(`---Результат задачи ${task}---`)
    console.log('Ожидаемый: ', taskResult.expectedResult)
    console.log('Из функции: ', taskResult.result)
    console.log('')
}


showTaskResult(4, Task4())

Ответ

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

function getResult(source) {
  const colors = ['green', 'yellow', 'red'];
  const events = new Map();
  const add = (point, color, delta) => {
    if (!events.has(point)) events.set(point, [0, 0, 0]);
    events.get(point)[color] += delta;
  };
  colors.forEach((color, index) => {
    for (const { start, end } of source[color]) {
      if (!(0 <= start && start < end && end <= 100)) throw new RangeError('Неверный интервал');
      add(start, index, 1); add(end, index, -1);
    }
  });
  const points = [...events.keys()].sort((a, b) => a - b);
  const active = [0, 0, 0], result = [];
  for (let i = 0; i + 1 < points.length; i++) {
    const point = points[i];
    events.get(point).forEach((delta, index) => { active[index] += delta; });
    const mnemo = colors.filter((_, index) => active[index] > 0);
    if (!mnemo.length) continue;
    const last = result[result.length - 1];
    if (last && last.end === point && last.mnemo.join() === mnemo.join()) last.end = points[i + 1];
    else result.push({ mnemo, start: point, end: points[i + 1] });
  }
  return result;
}

Интервалы трактуются как [start, end), точки нулевой длины не выводятся. Незакрашенные промежутки пропускаются. Счётчики корректны и при пересечении интервалов одного цвета. Исходный набор обходится один раз, сортировка событий даёт O(n log n); порядок цветов совпадает с примером.