CODEWITHSUNDEEP
algorithmrange
jsguy
jsguy

Reputation: 2179

You have a set of N ranges, is it possible to find whether the intersection is empty in O(n)?

I have a set of N ranges, where each range is in the form of [a,b] and both a, b are integers.

I would like to find whether their intersection is empty.

Without assuming anything about this set, would it be possible to do something in O(n) time?

Upvotes: 1

Views: 416

Answers (3)

rici
rici

Reputation: 241691

The usual problem with N ranges is to determine whether they are pairwise disjoint (which is O(N log N)) but here I think you are asking whether the intersection of all the ranges is empty. That can be solved in O(N) in the obvious way:

  1. Set R to the first range R1.
  2. For each subsequent range Ri, set R to the intersection of itself with Ri
  3. At the end, R will be the intersection. Check to see if it is empty.

That this works in O(N) relies on two facts:

  1. You can intersect two ranges in O(1).
  2. The intersection of two ranges is either empty or a range.

Both of these fall directly out of the fact that the intersection of two ranges [low1, high1] and [low2, high2] is [max(low1,low2), min(high1, high2)].

Upvotes: 4

Xline
Xline

Reputation: 812

A1 ∩ A2 ∩ ..., ∩ An = ( ( ( A1 ∩ A2) ∩ A3 ) ∩ .... ∩ An )

You stop intersecting when you encounter an empty set. Each pair takes O(1)

Upvotes: 0

Carsten
Carsten

Reputation: 18446

Try and see if the maximum of the lower limits is larger than the minimum of the upper limits. If the first is greater than the second, the intersection has to be empty. (If this is not obvious, I'll try to find or construct a proof.) If not, check if the resulting interval [max, min] contains elements of your choice (you didn't mention if you are looking for an interval in the integers, or real numbers, or what1.

Maximum and minimum of a list can both be found in linear time. So this will perform in O(N) time.

import numpy as np
ranges = np.array([[1, 5], [2, 3], [-1, 17], [15, 15]])

max = np.max(ranges[:,0])
min = np.min(ranges[:,1])

if max > min:
    print "definitely empty"
else:
    print "gotta check, but we've got the intersection now. it's [{0}:{1}]".format(max, min)

1 For the typical kinds of sets, say, reals or integers, this check should be O(1).

Upvotes: 1

Related Questions