how to get common range for several intervals

I am interested to find the common range for several intervals. This common range will not cover all these intervals. For example, for these data:

Data=[26 27
    22 23.3
    22.5 23.4
    22 23
    20 23.7
    21 23.5
    24 25.5
    24 24.5
    24 24.4];

The common range should be: [ 22.5 , 23 ]

I was using the second answer in this question. But it gives [ 24 , 24.4 ] as an output because its code is biased to find the smallest interval that's why it output [ 24 , 24.4 ] not [ 22.5 , 23 ]. Indeed, I am interested to find the common range containing as much intervals as can, that is the [ 22.5 , 23 ] for the example with data mentioned above.

[Torsten]

Assume you specify 10 intervals and their intersection is empty.

Assume further that for 8 intervals the intersection were [0,1000], but for 9 intervals the intersection would be only the point {1000}, you would prefer the solution with the one point ?

[Hussein Al Jebaei]

Depending on the application that I am working on, the intersection will not be empty. The data that I have are such that the example provided in the question. The intervals upper and lower limits are within 20-27.

As I mentioned in the question, there can be two common ranges for these data: [ 22.5 , 23 ] and [ 24 , 24.4 ]. I am interesetd in the first interval since it is the solution of 5 intervals. However, the second range is the solution of 3 intervals out of the 9.

[Torsten]

So you always prefer the solution with maximum number of intervals independent of the size of the intersection ?

[Hussein Al Jebaei]

Yes.

[Torsten]

That's a difficult optimization problem - not easily solved.

I'll think about it.

Do you already have a code that tells you if a set of intervals intersects and what the intersection is ?

Did you search in the File Exchange or got a code from your previous request ?

[Hussein Al Jebaei]

The code I used is from my previous query request.

In the File Exchange there are some files such as:

https://www.mathworks.com/matlabcentral/fileexchange/24254-interval-merging

https://www.mathworks.com/matlabcentral/fileexchange/31753-range-intersection

Those won't work for my application.

[Torsten]

What about

https://de.mathworks.com/matlabcentral/fileexchange/69367-interval-intersection

Note that in the first step, you only need a code that will tell you if a set of intervals have a common intersection or not.

The second step - determine the maximum number of intervals with common intersection if the intersection of all intervals is empty - is an optimization and a very special question, so won't be covered by any code available.

[Hussein Al Jebaei]

Thank you! This code is for two ranges A and B only. what if we have 10 intervals?

[Torsten]

Find intersection of I1 and I2.

Name it I.

Find intersection of I and I3.

Name it I.

...

Find intersection of I and I_n.

Make a loop.

The last I will be the intersection of all n intervals.

Answer 1

[Torsten]

Maybe not the most elegant solution, but it should work:

Data=[26 27
    22 23.3
    22.5 23.4
    22 23
    20 23.7
    21 23.5
    24 25.5
    24 24.5
    24 24.4];

S = sort(unique(Data(:)));
count = zeros(1,numel(S)-1);
for i = 1:numel(S)-1
  I1 = S(i);
  I2 = S(i+1);
  for j = 1:size(Data,1)
    if I1 >= Data(j,1) && I2 <= Data(j,2) 
      count(i) = count(i) + 1;
    end
  end  
end
k = max(count);
f = find(diff([false,count==k,false])~=0);
[~,p] = max(S(f(2:2:end))-S(f(1:2:end-1)));
  
disp("Number of Intervals from Data Matrix involved:")
k
disp("Maximum Common Interval is:")
S(f(2*p-1):f(2*p))

[Hussein Al Jebaei]

Thank you so much for your assitance! It is working.

Answer 2

[John D'Errico]

Please stop asking the same question over and over again.

Finding the sub-interval that covers the maximum number of intervals should be equivalent to a combinatoric search, where you will want to consider all possible lower bounds from the set of all lower bounds, then combine them with all possible upper bounds from the upper bounds of the same intervals. If you have n intervals, then this would be a search where you would need to check n^2 possible combinations of bounds. That is not too large, and would take a simple double loop to implement at worst.

First, what is the question? You want a new interval that is entirely contained within the largest number of intervals from the set.

In this example set:

Data=[26 27
    22 23.3
    22.5 23.4
    22 23
    20 23.7
    21 23.5
    24 25.5
    24 24.5
    24 24.4];
M = mean(Data,2);
W = (Data(:,2) - Data(:,1))/2;
plot([1 1]'*(1:length(M)),[M-W,M+W]','-o')
yline([22.5 23],'r')

There we see the interval you want is contained inside 5 of the data intervals.

We can find that sub-interval using a combinatoric search. The problem is, if you have many intervals, then this search will be time consuming if you used brute force. As well, there may be multiple solutions that cover the same number of data intervals. I assume they would be equally good, although then I would assume you would break ties because you would then ask for the longest such sub-interval.

In my eyes, then the solution would just use a simple loop, or even a double loop. But best would seem to be to just use meshgrid. See the code below.

[LU,intervalscovered,intervallength] = bestintersection(Data)

LU = 1×2

22.5000 23.0000

intervalscovered = 5

intervallength = 0.5000

This code will work nicely for up to perhaps several hundred intervals. More than that will become memory intensive, and a simple double loop might be best.

function [LU,intervalscovered,intervallength] = bestintersection(data)
  L = data(:,1);
  U = data(:,2);
  % how many data intervals
  n = numel(L);
  
  [I,J] = meshgrid(1:n);
  
  Li = L(I);
  Uj = U(J);
  
  % interval width
  Wij = Uj - Li;
  % ignore those with negative interval width
  ignor = Wij <= 0;
  Wij(ignor) = -inf;
  Li(ignor) = -inf;
  Uj(ignor) = inf;
  
  % how many data intervals does each such interval lie inside?
  overlapcount = sum((Li >= reshape(L,[1 1 n])) & (Uj <= reshape(U,[1 1 n])),3);
  
  % find the sub-interval with the maximum coverage. If there is more than
  % one such solution, we will choose the one with maximum interval width.
  intervalscovered = max(overlapcount,[],'all');
  ind = find(overlapcount == intervalscovered);
  
  if numel(ind) == 1
    % only one interval was found with the maximum data intervals covered.
    % It must be the preferred solution.
    LU = [Li(ind),Uj(ind)];
    intervallength = Wij(ind);
  else
    % choose the interval with maximum width, over those found
    [~,K] = max(Wij(ind))
    LU = [Li(ind(K)),Uj(ind(K))];
    intervallength = Wij(ind(K));
  end
  
end