2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.