Algoritma untuk meratakan rentang yang tumpang tindih

Saya mencari cara yang bagus untuk meratakan (membelah) daftar rentang angka yang berpotensi tumpang tindih. Masalahnya sangat mirip dengan pertanyaan ini: Cara tercepat untuk membagi rentang tanggal yang tumpang tindih , dan banyak lainnya.

Namun, rentangnya tidak hanya bilangan bulat, dan saya mencari algoritma yang layak yang dapat dengan mudah diimplementasikan dalam Javascript atau Python, dll.

Contoh Data:

Contoh Solusi:

Mohon maaf jika ini adalah duplikat, tetapi saya belum menemukan solusi.

Berjalan dari kiri ke kanan, menggunakan tumpukan untuk melacak warna apa yang Anda pakai. Alih-alih peta diskrit, gunakan 10 angka dalam dataset Anda sebagai break-point.

Dimulai dengan tumpukan kosong, dan pengaturan startke 0, loop sampai kita mencapai akhir:

• Jika tumpukan kosong:
  • Cari warna pertama mulai dari atau setelahnya start, dan dorong dan semua warna dengan peringkat lebih rendah ke tumpukan. Dalam daftar Anda yang rata, tandai bagian awal warna itu.
• lain (Jika tidak kosong):
  • Temukan titik awal berikutnya untuk warna dengan peringkat lebih tinggi pada atau setelahnya start, dan temukan akhir dari warna saat ini
    • Jika warna berikutnya dimulai lebih dulu, dorong dan apa pun yang lain dalam perjalanan ke tumpukan. Perbarui akhir warna saat ini sebagai awal dari yang satu ini, dan tambahkan awal warna ini ke daftar yang diratakan.
    • Jika tidak ada dan warna saat ini berakhir lebih dulu, atur startke akhir warna ini, keluarkan dari tumpukan, dan periksa warna berperingkat tertinggi berikutnya
      • Jika startberada dalam kisaran warna berikutnya, tambahkan warna ini ke daftar yang diratakan, mulai dari start.
      • Jika tumpukan kosong, lanjutkan loop (kembali ke titik peluru pertama).

Ini adalah mental yang diberikan mengingat data contoh Anda:

# Initial data.
flattened = []
stack = []
start = 0
# Stack is empty.  Look for the next starting point at 0 or later: "b", 0 - Push it and all lower levels onto stack
flattened = [ (b, 0, ?) ]
stack = [ r, b ]
start = 0
# End of "b" is 5.4, next higher-colored start is "g" at 2 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, ?) ]
stack = [ r, b, g ]
start = 2
# End of "g" is 12, next higher-colored start is "y" at 3.5 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, ?) ]
stack = [ r, b, g, y ]
start = 3.5
# End of "y" is 6.7, next higher-colored start is "o" at 6.7 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, ?) ]
stack = [ r, b, g, y, o ]
start = 6.7
# End of "o" is 10, and there is nothing starting at 12 or later in a higher color.  Next off stack, "y", has already ended.  Next off stack, "g", has not ended.  Delimit and continue.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, ?) ]
stack = [ r, b, g ]
start = 10
# End of "g" is 12, there is nothing starting at 12 or later in a higher color.  Next off stack, "b", is out of range (already ended).  Next off stack, "r", is out of range (not started).  Mark end of current color:
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12) ]
stack = []
start = 12
# Stack is empty.  Look for the next starting point at 12 or later: "r", 12.5 - Push onto stack
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, ?) ]
stack = [ r ]
start = 12
# End of "r" is 13.8, and there is nothing starting at 12 or higher in a higher color.  Mark end and pop off stack.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, 13.8) ]
stack = []
start = 13.8
# Stack is empty and nothing is past 13.8 - We're done.

Solusi ini tampaknya yang paling sederhana. (Atau setidaknya, yang paling mudah untuk dipahami)

Yang diperlukan hanyalah fungsi untuk mengurangi dua rentang. Dengan kata lain, sesuatu yang akan memberikan ini:

A ------               A     ------           A    ----
B    -------    and    B ------        and    B ---------
=       ----           = ----                 = ---    --

Yang cukup sederhana. Kemudian Anda dapat dengan mudah mengulangi masing-masing rentang, mulai dari yang terendah, dan untuk masing-masing, kurangi dari semua rentang di atasnya, pada gilirannya. Dan begitulah.

Berikut ini adalah implementasi dari range subtractor dengan Python:

def subtractRanges((As, Ae), (Bs, Be)):
    '''SUBTRACTS A FROM B'''
    # e.g, A =    ------
    #      B =  -----------
    # result =  --      ---
    # Returns list of new range(s)

    if As > Be or Bs > Ae: # All of B visible
        return [[Bs, Be]]
    result = []
    if As > Bs: # Beginning of B visible
        result.append([Bs, As])
    if Ae < Be: # End of B visible
        result.append([Ae, Be])
    return result

Menggunakan fungsi ini, sisanya dapat dilakukan seperti ini: ('span' berarti rentang, karena 'rentang' adalah kata kunci Python)

spans = [["red", [12.5, 13.8]],
["blue", [0.0, 5.4]],
["green", [2.0, 12.0]],
["yellow", [3.5, 6.7]],
["orange", [6.7, 10.0]]]

i = 0 # Start at lowest span
while i < len(spans):
    for superior in spans[i+1:]: # Iterate through all spans above
        result = subtractRanges(superior[1], spans[i][1])
        if not result:      # If span is completely covered
            del spans[i]    # Remove it from list
            i -= 1          # Compensate for list shifting
            break           # Skip to next span
        else:   # If there is at least one resulting span
            spans[i][1] = result[0]
            if len(result) > 1: # If there are two resulting spans
                # Insert another span with the same name
                spans.insert(i+1, [spans[i][0], result[1]])
    i += 1

print spans

Ini memberi [['red', [12.5, 13.8]], ['blue', [0.0, 2.0]], ['green', [2.0, 3.5]], ['green', [10.0, 12.0]], ['yellow', [3.5, 6.7]], ['orange', [6.7, 10.0]]], mana yang benar.

Jika cakupan data benar-benar mirip dengan data sampel Anda, Anda dapat membuat peta seperti ini:

map = [0 .. 150]

for each color:
    for loc range start * 10 to range finish * 10:
        map[loc] = color

Kemudian cukup berjalan melalui peta ini untuk menghasilkan rentang

curcolor = none
for loc in map:
    if map[loc] != curcolor:
        if curcolor:
            rangeend = loc / 10
        make new range
        rangecolor = map[loc]
        rangestart = loc / 10

Agar berfungsi, nilainya harus dalam kisaran yang relatif kecil seperti pada data sampel Anda.

Sunting: untuk bekerja dengan float sejati, gunakan peta untuk menghasilkan pemetaan tingkat tinggi dan kemudian merujuk ke data asli untuk membuat batas-batas.

map = [0 .. 15]

for each color:
   for loc round(range start) to round(range finish):
        map[loc] = color

curcolor = none
for loc in map
    if map[loc] != curcolor:

        make new range
        if loc = round(range[map[loc]].start)  
             rangestart = range[map[loc]].start
        else
             rangestart = previous rangeend
        rangecolor = map[loc]
        if curcolor:
             if map[loc] == none:
                 last rangeend = range[map[loc]].end
             else
                 last rangeend = rangestart
        curcolor = rangecolor

Inilah solusi yang relatif mudah di Scala. Seharusnya tidak terlalu sulit untuk port ke bahasa lain.

case class Range(name: String, left: Double, right: Double) {
  def overlapsLeft(other: Range) =
    other.left < left && left < other.right

  def overlapsRight(other: Range) =
    other.left < right && right < other.right

  def overlapsCompletely(other: Range) =
    left <= other.left && right >= other.right

  def splitLeft(other: Range) = 
    Range(other.name, other.left, left)

  def splitRight(other: Range) = 
    Range(other.name, right, other.right)
}

def apply(ranges: Set[Range], newRange: Range) = {
  val left     = ranges.filter(newRange.overlapsLeft)
  val right    = ranges.filter(newRange.overlapsRight)
  val overlaps = ranges.filter(newRange.overlapsCompletely)

  val leftSplit  =  left.map(newRange.splitLeft)
  val rightSplit = right.map(newRange.splitRight)

  ranges -- left -- right -- overlaps ++ leftSplit ++ rightSplit + newRange
}

val ranges = Vector(
  Range("red",   12.5, 13.8),
  Range("blue",   0.0,  5.4),
  Range("green",  2.0, 12.0),
  Range("yellow", 3.5,  6.7),
  Range("orange", 6.7, 10.0))

val flattened = ranges.foldLeft(Set.empty[Range])(apply)
val sorted = flattened.toSeq.sortBy(_.left)
sorted foreach println

applymengambil Setdari semua rentang yang telah diterapkan, menemukan tumpang tindih, lalu mengembalikan set baru dikurangi tumpang tindih dan ditambah rentang baru dan rentang yang baru dipisah. foldLeftpanggilan berulang kali applydengan masing-masing rentang input.

Simpan satu set rentang yang diurutkan berdasarkan mulai. Tambahkan rentang yang mencakup semuanya (-oo .. + oo). Untuk menambahkan rentang r:

let pre = last range that starts before r starts

let post = earliest range that starts before r ends

now iterate from pre to post: split ranges that overlap, remove ranges that are covered, then add r