Find the smallest number that is not in a list of intervals

Question

I have to find the smallest number that is not in a list of intervals. For example, i have a list: [(2, 6), (0, 3), (9, 10)]. I have to find the smallest number by checking all numbers from 0 to 10 until i find the smallest one that is not in any of these ranges. So, the number can't be between 2 and 6 (including both), 0 and 3, 9 and 10.

I've written a function and i can't get the right answer. I always get all first numbers that the program checks, but i just need the last one. And i don't understand why it doesn't work with return.

intervals = [(2, 6), (0, 3), (9, 10)]
def smallest_number(intervals):
   i = 0
   while True:
      for first, second in intervals:
         if i in range(first, second + 1):
            i += 1
            print(i)

print(smallest_number(intervals))

I expect the output 7, but i get a loop of 7's or numbers from 1 to 7, depending on where i put print(i).

Answer 1

Your code will print all the numbers that are in the intervals, not those that are not, before it ends in an infinite loop. Try this:

def smallest_number(intervals):
    i = 0
    while True:
        for first, second in intervals:
            if i in range(first, second + 1):
                i += 1
                break # break from inner loop
        else:
            break # break from outer loop
    return i # return number

Also, while if i in range(first, second + 1): is okay (and fast) in Python 3, I'd rather suggest using if first <= i <= second:

Or shorter, using next and any:

def smallest_number(intervals, max_ = 10):
    return next((i for i in range(max_ + 1)
                 if not any(first <= i <= second for first, second in intervals)),
                None) # None is default if none is found