# 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 & yellow
• [7,8] - red & yellow & green
• [8,9] - red & 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.

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.