Geek asks and answers

How to effectively cover intervals

I need your help. I have a problem (see picture). I allowed two arrays, and each of these arrays contains intervals with different lengths and real values, and I need to figure out how I got away by overlapping these intervals effectively.

I am open to ideas, or paper theory, or to concrete algorithms that will allow me to find a way out! I suppose that one way or another I will transform it into waves and block them.

Its very important, its for my thesis.

as an example, here in numbers, to better explain this:

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

The result will be a single array containing new intervals.

the second interval (array one and two) overlap.

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

I think of the "interval tree", but it is not enough, as I go with them.

picture

Thanks in advance!

+3
source share
6 answers

1) Put all your intervals in one array.

2) Sort this array by the lower boundary of each interval.

3) Scroll from the lower lower bound to the upper upper bound:

a) If the interval after this begins before it ends, merge them (delete the second and continue this to have an upper bound).

b) Repeat until the next interval begins after this.

4) Repeat until you reach the last interval.

+10
source

Here is the version in python (versions 2 and 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))

Conclusion:

[(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

, .

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

+1
/**
* 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;
    }   

}
0
# 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
0

JAVA : documenation

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

}
0

More articles:


All Articles