Algorithm for Intersection (or Merge) of Numerical

问题:

Let's say I have a list of ranges like this:

List A) 0 to 3, 9 to 14

List B) 1 to 4, 6 to 7, 14 to 16

List C) 15 (i.e., 15 to 15)

I'd like to get a merged list of these ranges where the result would look like this:

Merged Result List) 0 to 4, 6 to 7, 9 to 16

(notice that the result is a merging/intersection/union of Lists A, B, and C)

I'm sure there's an algorithm for this, but have no idea. Has anyone come across this before?

(pseudocode, or VB, would be great)

Adding a visual representation:

回答1:

Make array/list of pairs (Value, Flag = +1 for start or -1 for end of range)

Sort these pairs by Value (use Flag as secondary key in case of tie)

Make Counter = 0

Walk through sorted array, adding Flag to Counter

When Counter becomes non-zero, merged range begins.

When Counter becomes zero, merged range ends

P.S. If you want to merge "touching" intervals - account for Flag in comparator function during sorting when Value is the same - for example, (14;+1) before (14,-1)