View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Interval merging

4.0 | 2 ratings Rate this file 4 Downloads (last 30 days) File Size: 3.48 KB File ID: #24254 Version: 1.2

Interval merging


Bruno Luong (view profile)


25 May 2009 (Updated )

Merging intervals in the bracket form

| Watch this File

File Information

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.


This file inspired Range Intersection.

MATLAB release MATLAB 7.8 (R2009a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (6)
15 Jun 2015 Arbi

Arbi (view profile)

you should see this

Comment only
31 Jan 2015 Ulrik

Ulrik (view profile)

Your code can be optimized a bit to run even faster. (tested with the profiler)

function [lower,upper] = MergeBrackets(Left, Right)

% Detect when right < left (empty Ii), and later remove it (line #29, 30)
Right = Right(:);
Left = Left(:);

IdxKeep = Right>=Left;
Right = Right(IdxKeep);
Left = Left(IdxKeep);
% sort the rest by left bound
[Left,iorder] = sort(Left);
Right = Right(iorder);

% Allocate, as we don't know yet the size, we assume the largest case
lower = zeros(size(Left));
upper = zeros(size(Right));

% Nothing to do
if isempty(lower)

% Initialize
l = Left(1);
u = Right(1);
k = 0;
% Loop on brakets
for i=1:length(Left)
if Left(i) > u % new Jk detected
% Stack the old one
k = k+1;
lower(k) = l;
upper(k) = u;
% Reset l and u
l = Left(i);
u = Right(i);
u = max(u, Right(i));
% Stack the last one
k = k+1;
lower(k) = l;
upper(k) = u;
IdxKeep = true(k,1);
% Remove the tails
lower = lower(IdxKeep);
upper = upper(IdxKeep);

10 Jun 2011 Xavier Xavier

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

I submitted a faster method here

Comment only
03 Jul 2010 Xavier Xavier

Thank you very much, this is working perfectly!


Comment only
01 Jul 2010 Bruno Luong

Bruno Luong (view profile)

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


Comment only
30 Jun 2010 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.

22 Apr 2013 1.1

New feature, intersection of a set of interval-unions

23 Apr 2013 1.2

Simplified engine for RangeIntersection

Contact us