Array of overlaping ranges Consider that I have an array of ranges and I want to transform it to the new array that represents the ranges that any range is in.

Example:

Ranges: 
[red: [1,11], black: [15,16],yellow: [5,9], green: [7,8]]

Result:


[1,4] - red
[5,7] - red &amp; yellow
[7,8] - red &amp; yellow &amp; green
[8,9] - red &amp; yellow
[10,11] - red
[15,16] - black


My first thought was to use interval tree but the most implementations I found  want to ask tree by range and I want to explicitly list groups as shown in example.
Sort all coordinates of intervals (annotated with their significance), and scan them in order.

As an example, in your case you would get
$$
1^{+red},5^{+yellow},7^{+green},8^{-green},9^{-yellow},11^{-red},15^{+black},16^{-black}
$$
This immediately gives the decomposition into intervals $$(1,5),(5,7),(7,8),(8,9),(9,11),(11,15),(15,16)$$
with associated colors.

Note that this list differs from your output, since you sometimes move the endpoint back by 1 point for some unspecified reason.