title: fast algorithm for merging overlapping intervals
body: <p>I am trying to program a fast enough algorithm to merge intervals with values.</p>
  
  <p>For example, there are 3 intervals (Including from and to):</p>
  
  <ol>
  <li><code>{from:1, to: 3, amount: 1}</code></li>
  <li><code>{from:5, to: 7, amount: 1}</code></li>
  <li><code>{from:2, to: 6, amount: 1}</code></li>
  </ol>
  
  <p>Result:</p>
  
  <ol>
  <li><code>{from:1, to: 1, amount: 1}</code></li>
  <li><code>{from:2, to: 3, amount: 2}</code></li>
  <li><code>{from:4, to: 4, amount: 1}</code></li>
  <li><code>{from:5, to: 6, amount: 2}</code></li>
  <li><code>{from:7, to: 7,amount: 1}</code></li>
  </ol>
  
  <p>When the number of intervals reaches 5000, then the calculations in my algorithm can take about one minute. (in the case when each new interval on the merge overlaps a large number of others).
  Maybe someone can advise some already known algorithm that is suitable for this task, or maybe he has already encountered a similar problem and will share his solution?</p>
  
  <p><a href="https://i.stack.imgur.com/jcHiY.png" rel="nofollow noreferrer">input</a>
    <a href="https://i.stack.imgur.com/jojSu.png" rel="nofollow noreferrer">result</a></p>
  
  <pre><code>       function mergeingIntervals(intervals: IInterval[]): IInterval[] {
              //sort by length
              intervals.sort((a, b) =&gt; b.to - b.from - a.to + a.from);
              const result = [intervals[0]];
              intervals.forEach(interval =&gt; addInterval(result, interval));
              result.sort((a, b) =&gt; a.from - b.from);
  
              return result;
          }
  
          function addInterval(result: IInterval[], interval: IInterval): void {
              const firstIntersectionIndex = result.findIndex(row =&gt;
                  row.from &gt;= interval.from &amp;&amp; row.to &lt;= interval.to ||
                  row.from &gt;= interval.from &amp;&amp; row.from &lt;= interval.to ||
                  row.from &lt;= interval.from &amp;&amp; row.to &gt;= interval.to ||
                  row.to &gt;= interval.from &amp;&amp; row.to &lt;= interval.to,
              );
  
              if (firstIntersectionIndex === -1) {
                  const indexToInsertInto = result.findIndex(row =&gt; row.from &gt; interval.to);
                  if (indexToInsertInto !== -1) {
                      result.splice(indexToInsertInto, 0, interval);
                  } else {
                      result.unshift(interval);
                  }
              } else {
                  const valueToMergeInto = result[firstIntersectionIndex];
                  if (valueToMergeInto.from &lt;= interval.from &amp;&amp; valueToMergeInto.to &gt;= interval.to) {
                      const newIntervals: IInterval[] = [];
                      if (valueToMergeInto.from !== interval.from) {
                          newIntervals.push({
                              from: valueToMergeInto.from,
                              to: subtractHour(interval.from),
                              value: valueToMergeInto.value,
                          });
                      }
                      newIntervals.push({
                          from: interval.from,
                          to: interval.to,
                          value: interval.value + valueToMergeInto.value,
                      });
                      if (valueToMergeInto.to !== interval.to) {
                          newIntervals.push({
                              from: addHour(interval.to),
                              to: valueToMergeInto.to,
                              value: valueToMergeInto.value,
                          });
                      }
                      result.splice(firstIntersectionIndex, 1, ...newIntervals);
                  } else {
                      let count = 1;
                      result.slice(firstIntersectionIndex).forEach(sumValue =&gt; {
                          if (sumValue.to &lt;= interval.to) {
                              count++;
                              return false;
                          } else {
                              return true;
                          }
                      });
                      if (count &lt; 5) {
                          result.splice(firstIntersectionIndex, 1);
                          const newIntervals: IInterval[] = [];
                          if (interval.from &lt; valueToMergeInto.from) {
                              newIntervals.push({
                                  from: interval.from,
                                  to: subtractHour(valueToMergeInto.from),
                                  value: interval.value,
                              }, {
                                  from: valueToMergeInto.from,
                                  to: Math.min(valueToMergeInto.to, interval.to),
                                  value: valueToMergeInto.value + interval.value,
                              });
                              if (interval.to !== valueToMergeInto.to) {
                                  newIntervals.push({
                                      from: addHour(Math.min(valueToMergeInto.to, interval.to)),
                                      to: Math.max(valueToMergeInto.to, interval.to),
                                      value: valueToMergeInto.to &lt; interval.to ? interval.value : valueToMergeInto.value,
                                  });
                              }
                          } else {
                              if (interval.from !== valueToMergeInto.from) {
                                  newIntervals.push({
                                      from: valueToMergeInto.from,
                                      to: subtractHour(interval.from),
                                      value: valueToMergeInto.value,
                                  });
                              }
                              newIntervals.push({
                                  from: interval.from,
                                  to: Math.min(interval.to, valueToMergeInto.to),
                                  value: interval.value + valueToMergeInto.value,
                              });
                              if (interval.to !== valueToMergeInto.to) {
                                  newIntervals.push({
                                      from: addHour(Math.min(valueToMergeInto.to, interval.to)),
                                      to: Math.max(valueToMergeInto.to, interval.to),
                                      value: valueToMergeInto.to &lt; interval.to ? interval.value : valueToMergeInto.value,
                                  });
                              }
                          }
                          newIntervals.forEach(period =&gt; addInterval(result, period));
                      } else {
                          const newIntervals: IInterval[] = [];
                          if (interval.from &lt; valueToMergeInto.from) {
                              newIntervals.push({
                                  from: interval.from,
                                  to: subtractHour(valueToMergeInto.from),
                                  value: interval.value,
                              }, {
                                  from: valueToMergeInto.from,
                                  to: Math.min(valueToMergeInto.to, interval.to),
                                  value: interval.value,
                              });
                              if (interval.to !== valueToMergeInto.to) {
                                  newIntervals.push({
                                      from: addHour(Math.min(valueToMergeInto.to, interval.to)),
                                      to: Math.max(valueToMergeInto.to, interval.to),
                                      value: valueToMergeInto.to &lt; interval.to ? interval.value : 0,
                                  });
                              }
                          } else {
                              if (interval.from !== valueToMergeInto.from) {
                                  newIntervals.push({
                                      from: valueToMergeInto.from,
                                      to: subtractHour(interval.from),
                                      value: 0,
                                  });
                              }
                              newIntervals.push({
                                  from: interval.from,
                                  to: Math.min(interval.to, valueToMergeInto.to),
                                  value: interval.value,
                              });
                              if (interval.to !== valueToMergeInto.to) {
                                  newIntervals.push({
                                      from: addHour(Math.min(valueToMergeInto.to, interval.to)),
                                      to: Math.max(valueToMergeInto.to, interval.to),
                                      value: valueToMergeInto.to &lt; interval.to ? interval.value : 0,
                                  });
                              }
                          }
                          const valuesToMergeIntoArray = result.splice(firstIntersectionIndex, count, ...newIntervals);
                          valuesToMergeIntoArray.forEach(period =&gt; addInterval(interval, period));
                      }
                  }
              }
          }
  </code></pre>