Interval merging

Merging intervals in the bracket form

Description

A handily simple function for a merging task:

Given N input closed intervals in bracket form:
Ii := [left(i),right(i)], i = 1,2...,N (mathematical notation).

The set union{Ii) can be written as a canonical partition by intervals Jk; i.e., union{Ii) = union(Jk), where Jk are M intervals (with M<=N, so the partition is minimum cardinal), and {Jk} are disjoint to each other (their intersections are empty).

This function returns Jk = [lower(k),upper(k)], k=1,2,...M, in the ascending sorted order.

• Acknowledgements: This submission has inspired the following:; Range intersection
• MATLAB release: MATLAB 7.8 (R2009a)

[Xavier Xavier]

Hello Bruno!

Thanks for this function, it's really usefull.
But now i have to do the intersection of intervals.
For example:
u stands for union, n stands for intersection
A=[0 2] u [6 9]
B=[1 7] u [8 12]
C=A n B = [1 2] u [6 7] u [8 9]

Do you have a function which is able to do that?
My problem is that A and B can be the union of N intervals so the shape of C is variable.
Cheers
Xavier

[Bruno Luong]

Hi Xavier,

You could do this ([lower(i), upper(i)] will compose C):

Aleft=[0 6];
Aright=[2 9];
Bleft=[1 8];
Bright=[7 12];

iitersect = @(i,j) deal(max([Aleft(i) Bleft(j)]),min([Aright(i) Bright(j)]));
[I J]=ndgrid(1:numel(Aleft),1:numel(Bleft));
[left right]=arrayfun(iitersect, I, J);
[lower upper] = MergeBrackets(left, right);

Bruno

[Xavier Xavier]

Thank you very much, this is working perfectly!

Regards
Xavier

[Xavier Xavier]

The method describe above is working really well but is time consuming.

I submitted a faster method here
http://www.mathworks.com/matlabcentral/fileexchange/31753