python algorithm: how to efficiently find if two integer sets are intersected?

Given a set [2004, 2008], what is the fastest way to find if this set is intersected with other sets?

Actually I am dealing a problem with database, the table has 2 columns, one is the lower bound, the other one is the higher bound. The task is to find all the intersected rows with the given 2 tuple(like [2004,2008]).

I am using mon开发者_StackOverflow中文版godb, is this intrinsically supported(I mean have keywords to do it). I have large user base, so I want this task to be completed as fast as possible.

EDIT: To stat more clear, a database table contains following rows:

20 30
10 50
60 90
...

Given the input (25 40) range, I want to return the rows which represent a range, have intersection with the given range.

so return is: (20 30),(10 50)

I don't know MongoDB at all, but you're basically looking for

SELECT * from the_table where not (lower_bound > 2008 or upper_bound < 2004).

Try this, assuming low and high are your bound fields:

db.ranges.find({'low': {'$lt': self.high}, 'high': {'$gt': self.low}})

Substitute $lte and $gte if you want your query to be inclusive rather than exclusive.

MongoDB does not support intersection. Perform intersection on the Python level using the intersection() API of sets.

Since you're dealing with lower bounds and upper bounds, you can just check bounds.

def intersects(this, others):
    upper, lower = this
    return [[u, l] for u, l in others 
            if (l < upper < u) or (l < lower < u)]

I don't know MongoDB but if you could implement that logic in the database, I can't help but think that it would be faster.

You could use a mongodb query with a Javascript expression (assuming lowerbounds and upperbounds are the limits of the set being intersected):

f = function() { return this.lower <= upperbounds && this.upper >= lowerbounds; }
db.ranges.find(f);

This should handle all cases including when [this.lower, this.upper] is a superset or proper subset of [lowerbounad, upperbounds].