как эффективно перекрывать интервалы

Question

Мне нужна ваша помощь, у меня проблема (см. Рисунок), я, скажем, два массива, и каждый из этого массива содержит интервалы с разной длиной и реальными значениями, и мне нужно выяснить, как я перекрыл эти интервалы эффективно.

Я открыт для идей, теории бумаги или конкретных алгоритмов, которые позволят мне найти выход! Я думаю о том, чтобы как-то преобразовать это в волны и перекрыть их.

Это очень важно, это для моей диссертации.

в качестве примера, здесь в цифрах, чтобы объяснить это лучше:

1. Массив: 1-2, 5-7, 9-12
2. Массив: 3-4, 5-6, 13-17

Результатом будет один массив, содержащий новые интервалы.

второй интервал (Массив один и два) перекрываются.

массив результатов: 1-2, 3-4, 5-7, 9-12, 13-17

Я думаю о "интервальном дереве", но недостаточно того, как я ушел, объединить их.

Заранее спасибо!

Answer 1

1) Поместите все ваши интервалы в один массив.

2) Сортировать этот массив по нижней границе каждого интервала.

3) Проходить через интервалы от нижней нижней границы до верхней верхней границы:

a) Если интервал после этого начинается до того, как этот заканчивается, объедините их (удалите второй и расширьте этот, чтобы иметь верхнюю границу).

б) Повторяйте до следующего интервала, начинающегося после его окончания.

4) Повторяйте, пока не достигнете последнего интервала.

Answer 2

Вот версия на python (версии 2 и 3):

def aggregate(data):
    data.sort()
    i = 0
    while i < len(data) - 1:
        while i < len(data) - 1 and data[i][1] >= data[i+1][0]:
            data[i] = (data[i][0], max(data[i][1], data[i+1][1]))
            data.pop(i+1)
        i += 1

if __name__ == '__main__':
    itervals = [(1,2), (5,7), (9,12), (3,4), (5,6), (13,17)]

    formatted = lambda vals: '[{}]'.format(', '.join('({}-{})'.format(
                                                   iterval[0], iterval[1])
                                                   for iterval in sorted(vals)))
    print(formatted(itervals))
    aggregate(itervals)
    print(formatted(itervals))

Вывод:

[(1-2), (3-4), (5-6), (5-7), (9-12), (13-17)]
[(1-2), (3-4), (5-7), (9-12), (13-17)]

Примечание: это мутирует список кортежей на месте.Немного более общий, который будет работать со списком итераций, можно сделать, изменив строку:

data[i] = type(data[i])((data[i][0], max(data[i][1], data[i+1][1])))

В качестве альтернативы, если вы знаете, что у вас есть список изменяемых итераций, вы можете использовать:

data[i][1] = max(data[i][1], data[i+1][1])

Альтернативная версия, за которой может быть немного легче следовать, это:

def aggregate(data):
    if not data:
        return data

    inputs = sorted(data)
    result = [inputs[0]]

    for next0, next1 in inputs[1:]:
        last0, last1 = result[-1]
        if next0 <= last1:
            result[-1][1] = max(next1, last1)
        else:
            result.append([next0, next1])

    return result

Обратите внимание, что эта версия предназначена для списка списков.

Answer 3

#include <vector>
using namespace std;

struct INTERVAL {
    int a; 
    int b;
};

// v is a sorted vector of intervals (a<=b)
// i is an interval (a<=b) to be merged with v, 
vector<INTERVAL> merge(vector<INTERVAL>& v, INTERVAL& i)
{
    bool fMerged=false; // merged flag
    INTERVAL r=i; // merged interval
    vector<INTERVAL> out; // out vector
    vector<INTERVAL>::size_type k=0; // iterator 

    for(k=0; k<v.size(); ++k) { 
        if (fMerged || v[k].b < r.a) {          
            out.push_back(v[k]); // v[k] comes first
        } 
        else if (r.b<v[k].a) {
            out.push_back(r); // r comes first
            out.push_back(v[k]);
            fMerged=true; // copy rest;
        }
        else { // intervals overlap, merge into r
            r.a=min(v[k].a,r.a); 
            r.b=max(v[k].b,r.b);
        }
    }
    // interval not merged, append to vector
    if (!fMerged) out.push_back(r);
    return out;
}

это может быть один из способов сделать это

Answer 4

JAVA-версия для этого: Исходная документация

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);
        }
    }

}

Answer 5

# Python implementation of http://www.geeksforgeeks.org/merging-intervals/

# Expects a list of (start,end) tuples
def merge_intervals(a):

    # Handle empty list correctly
    if len(a) == 0:
        return []

    # Operate on a copy so the original array is left untouched
    a = list(a)

    # Sort by lower bound
    a.sort()

    # Create stack from first interval
    b = [ a[0] ]

    # Loop through remaining intervals - either merge with top of stack or add
    for idx in xrange(1, len(a)):

        # References to top of stack and current in loop
        previous, current = b[-1], a[idx]

        # New interval if not overlapping
        if previous[1] < current[0]:
            b.append( current )

        # Merge if overlapping (if expands interval)
        elif previous[1] < current[1]:
            b.pop()
            b.append(( previous[0], current[1] ))

    # Return list of merged intervals
    return b

# Test case
if __name__ == '__main__':
    data = [ (1,5), (2,3), (4,6), (7,10), (8,12) ]
    from random import shuffle
    shuffle(data)
    print 'BEFORE', data
    data = merge_intervals(data)
    print 'AFTER', data

Answer 6

/**
* sort the interval based on the start time
* push the first interval to stack
* compare each interval start time with end time of top of stack
* if interval i th start time is more than  than start and end time of top of stack
* do nothing
* if interval i th  start time is between start and end time of top of stack then
*    update top of stack with ith interval end time
*
*/

import java.util.Stack;
import java.util.Arrays;



public class MergeInterval{

    private static  Stack<Interval> st = new Stack<Interval>();

    class Interval implements Comparable<Interval>{

        public int startTime;
        public int endTime;

        public Interval(int startTime, int endTime){
            this.startTime=startTime;
            this.endTime=endTime;
        }

        @Override
        public int compareTo(Interval i){

            if(startTime <=i.startTime) return 0;
            return 1;
        }

        public boolean canMerge(Interval m){

            if((startTime<=m.startTime) && (endTime>=m.startTime)) return true;
            else return false;
        }

        public String toString(){
            return ("{ "+startTime+" , "+endTime+" } ");
        }
    } 


    private static void findOverlapping(Interval[] setOne){

        //System.out.println(Arrays.toString(setOne));
        Arrays.sort(setOne);
        //System.out.println(Arrays.toString(setOne));
        st.push(setOne[0]);

        for(int i=1;i<setOne.length;i++){

            Interval in = st.peek();

            if(in.canMerge(setOne[i])){
                in.endTime=setOne[i].endTime;
            }else{
                st.push(setOne[i]);
            }

        }

        System.out.println(Arrays.toString(st.toArray()));


    }



    public static void main(String[] args) {

        MergeInterval m = new MergeInterval();
         Interval[] setOne = m.populate();


        findOverlapping(setOne);
    }

    public Interval[]  populate(){

        Interval[] setOne = new Interval[4];
        for(int i=0;i<4;i++){
            setOne[i]=new Interval(1,3);
        }
        setOne[0]=new Interval(1,3);
        setOne[1]=new Interval(2,4);
        setOne[2]=new Interval(5,7);
        setOne[3]=new Interval(6,8);

        return setOne;
    }   

}