wie man Intervalle effizient überschneidet

Question

Ich benötige Ihre Hilfe, ich habe ein Problem (siehe Bild), ich habe sagen wir zwei Arrays und jeder dieser Array enthält Intervalle mit unterschiedlicher Länge und realen Werten und ich muss herausfinden, wie ich bin gegangen überlappen diese Intervalle effizient.

Ich bin offen für Ideen, oder Papiertheorie oder konkrete Algorithmen, die mich einen Ausweg finden lassen! Ich denke darüber nach, dies irgendwie in Wellen zu transformieren und diese zu überlagern.

Das ist sehr wichtig, denn es geht um meine Diplomarbeit.

als Beispiel, hier in Zahlen, um es besser zu erklären:

1. Reihe: 1-2, 5-7, 9-12
2. Array: 3-4, 5-6, 13-17

Das Ergebnis ist dann ein einziges Array, das die neuen Intervalle enthält.

Sekundenintervall (Array eins und zwei) überschneiden sich.

Ergebnis Array: 1-2, 3-4, 5-7, 9-12, 13-17

Ich denke über "Intervall Baum", aber es ist nicht ausreichend, wie ich bin gegangen verschmelzen sie.

Vielen Dank im Voraus!

Answer 1

JAVA Version, um dies zu erreichen: Quellendokumentation

public class MergeRange {
    public class Range{
        public int start;
        public int end;
        public Range(int s, int e){
            start = s;
            end = e;
        }

        @Override
        public String toString() {
            return "[" + start + "," + end + "]";
        }

        @Override
        public boolean equals(Object o) {  
            if (o == this) {
                return true;
            }
            if (!(o instanceof Range)) {
                return false;
            }
            Range c = (Range) o;
            return start == c.start && end == c.end;             
        }
    }

    //compare two range by start, used to sort list of ranges by their starts
    public class RangeComparator implements Comparator<Range> {
        public int compare(Range range1, Range range2) { 
            return Integer.compare(range1.start, range2.start);
        }
    }

    public List<Range> merge(List<Range> ranges){
        if (ranges.size() < 2){
            return ranges;
        }

        ranges.sort(new RangeComparator());
        List<Range> result = new ArrayList<Range>();
        result.add(ranges.get(0));

        for (int i = 1; i < ranges.size(); i++){
            Range lastAdded = result.get(result.size() - 1);
            result.remove(result.size() - 1);
            List<Range> newRanges = merge(lastAdded, ranges.get(i));
            result.addAll(newRanges);           
        }

        return result;

    }
    //merge two ranges where range1.start <= range2.start
    private List<Range> merge(Range range1, Range range2){
        Assert.assertTrue(range1.start <= range2.start);

        if (range1.end < range2.start){
            return Arrays.asList(range1, range2);
        } else{
            Range result = new Range(range1.start, Math.max(range1.end, range2.end));
            return Arrays.asList(result);
        }
    }

}