алгоритм – Merging segments

Question:

At the input there is a list of segments of some (continuous) axis (numerical or time, it does not matter), each segment is represented by a pair of (ordered) coordinates – the beginning and end (these points also belong to the segment).

It is necessary to merge all intersecting segments and get at the output a list of segments that do not have intersections (but this new list should not have points that were not in the segments at the input).

For example, we have at the input:

[1; 5]
[2; 4]
[7; 9]
[3; 6]

then the output should be:

[1; 6] // здесь слиты [1; 5], [2; 4], [3; 6]
[7; 9]

implemented an algorithm like this:

function merge(segments) {
  while (true) {
    const newSegments = [];
    for (const x of segments) {
      let found = false;
      for (const y of newSegments) {
        if (x.end >= y.start && x.start <= y.end) {
          y.start = Math.min(y.start, x.start);
          y.end = Math.max(y.end, x.end);
          found = true;
          break;
        }
      }
      if (!found) newSegments.push(x);
    }
    if (segments.length == newSegments.length) break;
    segments = newSegments;
  }
  return segments;
}

function print(segments) {
  console.log(segments.map(s => `[${s.start}; ${s.end}]`).join(' '));
}

let segments = [
  { start: 1, end: 5 },
  { start: 2, end: 4 },
  { start: 7, end: 9 },
  { start: 3, end: 6 }
];

print(segments);
print(merge(segments));

It works but has O(n³) complexity.
Is it possible to write a better solution?

There is an idea: sort the input list and somehow adapt the scanning line method; but I still can't figure out how to implement it.

Answer:

Sorting by the left dot is the correct first step, we get:

[1; 5]
[2; 4]
[3; 6]
[7; 9]

Next, we compare the first segment with the second – the beginning of the second falls into the first segment, so we merge the segments: the beginning will be the beginning of the first, and the end will be max(the end of the first, the end of the second), we get [1; 5] .

[1; 5]
[3; 6]
[7; 9]

We also merge [1; 5] and [3; 6] in [1; 6]

[1; 6]
[7; 9]

[1; 6] and [7; 9] do not intersect, so we fix [1; 6] no other segment intersects with it, and we repeat all actions starting from [7; 9]

sorting complexity O(n log(n)) , merge complexity O(n) total O(n log(n))