Overlapping time-intervals

I have two date-time arrays a and b.

a for start time and b for end time (above horizontal line on the picture).

What is the way to parse them and get what is beneath horizontal line on the picture?

Answer 1

[David Goodmanson]

Hi Rostislav

It looks like you want the union of closed intervals. Here is some code that I think does the job. When the ends of intervals have the same value, it works because the sort function is stable and preserves ordering for ties.

% Nx2 matrix of endpoints x1, x2 of intervals
x = [8 10; 2 4; 4 5; 5 7; 9 11; 15 16; 14 17; 10 12]

% -----plot it first
nline  = repmat((1:size(x,1))',1,2);
plot(x',nline','o-')
ylim([-.5*nrow 1.5*nrow])

% ----- find union of intervals
x = sort(x,2);
nrow = size(x,1); 
[x ind] = sort(x(:));
n = [(1:nrow) (1:nrow)]';
n = n(ind);
c = [ones(1,nrow) -ones(1,nrow)]';
c = c(ind);
csc = cumsum(c);          % =0 at upper end of new interval(s)
irit = find(csc==0);
ilef = [1; irit+1];
ilef(end) = [];           % no new interval starting at the very end 

% y matrix is start and end points of the new intervals, y1,y2
%
% ny matrix is the corresponding indices of the start and end points
% in terms of what row of x they occurred in.

   y = [x(ilef) x(irit)]
  ny = [n(ilef) n(irit)]

[Rostislav Teryaev]

Thank you for your reply. Works like a charm! I did my one with loops, but your many times faster.

function [ a,b ] = intervalsSort( a, b )
tf = 1;
f = 1;

[a, ind] = sort(a);
b = b(ind);

for i = 1:length(a)
    if i == 1
        c(1) = a(1);
        d(1) = b(1);
    else
        f = 1;
        for j = 1:length(c)
            if c(j)<=a(i) & a(i)<=d(j)
                if  d(j) < b(i)
                    d(j) = b(i);
                end
                f = 0;
            end
        end
        if f
            c = [c a(i)];
            d = [d b(i)];
        end
    end
end

a = c;
b = d;
end

[Ted Shultz]

This is really great code. I fixed a small type, and added comments so others can learn from it as well.

intervalsIn = [8 10; 2 4; 4 5; 5 7; 9 11; 15 16; 14 17; 10 12]
% -----plot it first
nline  = repmat((1:size(intervalsIn,1))',1,2);
nrow = size(intervalsIn,1);
plot(intervalsIn',nline','o-')
ylim([-.5*nrow 1.5*nrow])

% ----- find union of intervals
intervalsIn = sort(intervalsIn,2);          % make the pairs always increasing pairs
[intervalsIn, ind] = sort(intervalsIn(:));  % sorts all the input values, and keepts track of how they moved around
c = [ones(1,nrow) -ones(1,nrow)]';          % this is a matrix that keeps track of when intervals start (1) and stop (-1)
c = c(ind);                                 % put in order of occurrence  
csc = cumsum(c);                            %sum up starts (1) and stops (-1) , will be =0 at upper end of new interval(s)
irit = find(csc==0);                        % find index locations of 0 (ends of intervals)
ilef = [1; irit+1];                         % start of intervals index is at the very start (1) and one after all the other ends
ilef(end) = [];                             % no new interval starting at the very end 

% spansOut matrix is start and end points of the new intervals, y1,y2
spansOut = [intervalsIn(ilef) intervalsIn(irit)]

Answer 2

[Hung Doan]

nrow is undefined in the initial plotting but other than that, works like a charm!

[Rostislav Teryaev]

I want to mention that poposed solution is very nice, but I remember that it has some kind of a bug. I can not point in which case, but I faced it in my project which I was doing that times. My solutions is slower but did not gave an error.

You can use any solution you want, but consider what I said.

[Ted Shultz]

Small typo in original answer, code could be be:

intervalsIn = [8 10; 2 4; 4 5; 5 7; 9 11; 15 16; 14 17; 10 12]
% -----plot it first
nline  = repmat((1:size(intervalsIn,1))',1,2);
nrow = size(intervalsIn,1);
plot(intervalsIn',nline','o-')
ylim([-.5*nrow 1.5*nrow])

% ----- find union of intervals
intervalsIn = sort(intervalsIn,2);          % make the pairs always increasing pairs
[intervalsIn, ind] = sort(intervalsIn(:));	% sorts all the input values, and keepts track of how they moved around
c = [ones(1,nrow) -ones(1,nrow)]';          % this is a matrix that keeps track of when intervals start (1) and stop (-1)
c = c(ind);                                 % put in order of occurrence  
csc = cumsum(c);                            %sum up starts (1) and stops (-1) , will be =0 at upper end of new interval(s)
irit = find(csc==0);                        % find index locations of 0 (ends of intervals)
ilef = [1; irit+1];                         % start of intervals index is at the very start (1) and one after all the other ends
ilef(end) = [];                             % no new interval starting at the very end 

% spansOut matrix is start and end points of the new intervals, y1,y2
spansOut = [intervalsIn(ilef) intervalsIn(irit)]