Dividi intervalli sovrapposti in tutti gli intervalli univoci

Question

Dividi intervalli sovrapposti in tutti gli intervalli univoci

#1 da (6 voti)

3

Sto provando a dividere un numero dinamico di intervalli con attributi associati, in modo che ogni volta che 2 o più intervalli si sovrappongono, le sezioni che si sovrappongono sono divise in intervalli univoci con la combinazione di tutti gli attributi sovrapposti. Per essere più specifici, dì che ho

1-10 - attributes a
7-12 - attributes b
9-15 - attributes c

Voglio renderlo

1-6 - attributes a
7-8 - attributes a, b
9 - 10 - attributes a,b,c
11-12 - attributes b,c
13-15 - attributes c

In realtà si riduce ad applicare lo stile agli intervalli in Open Office XML, ma credo che la logica sottostante possa essere risolta per qualsiasi scenario. Grazie per qualsiasi consiglio su come affrontare questo. Userò node / javascript, ma penso che qualsiasi linguaggio che dimostri il metodo sia sufficiente.

algorithms node.js

posta edencorbin 29.12.2017 - 01:56

fonte

1 risposta

Leggi altre domande sui tag algorithms node.js

L'implementazione di INotifyPropertyChanged su un controllo personalizzato è una cattiva pratica? Esiste un nome per poter trovare rapidamente il codice pertinente? [chiuso]

score 6 · Answer 1

Ecco cosa farei:

Crea una serie di terzine (n, attr, e), con due elementi per ogni intervallo dato. Uno codifica il punto iniziale e avrà e = false, l'altro codifica il punto finale e avrà e = true.

Nel tuo esempio, avrai [(1, a, falso), (10, a, vero), (7, b, falso), (12, b, vero), (9, c, falso) , (15, c, true)].

Ordina questo array su n ed e lessicograficamente (assumendo false < true)

Ora hai [(1, a, falso), (7, b, falso), (9, c, falso), (10, a, vero), (12, b, vero), (15, c, true)]

Ora fai un passaggio attraverso l'array ordinato, mantenendo il set "attuale" di attributi S (che, all'inizio, è vuoto). In ogni passaggio, aggiornare S e quindi restituire l'intervallo tra i due elementi consecutivi dell'array (regolando gli endpoint di 1 se necessario e saltando gli intervalli vuoti). In altre parole, se hai una coppia di terzine consecutive (n, a, e) e (m, b, f), il passo è:
- Se e = false, aggiungi a a S. Se e = true, togli una a da S.
- Definisci n '= n se e = falso o n' = n + 1 se e = vero
- Definisci m '= m-1 if f = false o m' = m if f = true
- Se n '< = m', output (n ', m', S), altrimenti non restituisce nulla.

Nel nostro esempio, l'output sarà [(1,6, {a}), (7,8, {a, b}), (9,10, {a, b, c}), (11 , 12, {b, c}), (13,15, {c})].