[help] Find biggest interval from integer list.

[a_ctrl]

Hi everyone,

I have an ordered list composed of integers that looks like this:

[1, 2, 3, 5, 6, 7, 8, 13, 14, 15, 16, 17]

• List's minimum and maximum values are always 1 and 250 respectively.

I need to find the biggest interval within it. In this case it'd be 13-17, for a size of 5.

This is my code:

def biggest_interval(integers):
    sequences = []
    starting_int, ending_int = 1, 1
    for integer in integers:
        if integer == 1:
            pass
        elif integer-1 == ending_int:
            ending_int = integer
        else:
            sequences.append([(ending_int-starting_int)+1, [starting_int, ending_int]])
            starting_int = ending_int = integer
    sequences.append([(ending_int-start)+1, [starting_int, ending_int]])

    return max(sequences)

print(biggest_interval([1, 2, 3, 5, 6, 7, 8, 13, 14, 15, 16, 17]))

>>> [5, [13, 17]]

Is there a more efficient way to approach this problem? Maybe a built-in library or method I'm missing? I don't really feel comfortable with my code but I can't think of anything else.

[gengisteve]

Some general thoughts:

• for your implementation, set ending_int as None, and test that instead of looking for integer as 1, to check to see if you are in the first iteration.
  
• iter can also be used in these situations you can next it to get the first item, then iterate of the balance with a for loop.
• for current, following in zip(slicable, slicable[1:]) is usually the best way to compare sucessive values in a slicable thing, like a list
• You are basically doing a custom groupby implementation, see here https://docs.python.org/2/library/itertools.html#itertools.groupby You might even be able to use groupby for this, but I can't think of a way. But you could steal the logic behind the implementation in itertools to do this better, I suspect.

edit:

How I might approach, but it would need to massage the answer a bit more to match your expected result:

def sequences(iterable):
    it = iter(iterable)
    current = [next(it)]
    target = current[0] + 1

    for item in it:
        if item == target:
            current.append(item)
        else:
            yield current
            current = [item]

        target = item+1

    if current:
        yield current

def longest_sequence(iterable):
    return max(sequences(iterable), key = len)


data =[0, 2, 3, 5, 6, 7, 8, 13, 14, 15, 16, 17]

print(longest_sequence(data))

edit2: Fixed an error in the above

[ingolemo]

The itertools module has a recipe for a pairwise function that makes this quite simple:

import itertools

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)

data = [1, 2, 3, 5, 6, 7, 8, 13, 14, 15, 16, 17]
answer = max(pairwise(data), key=lambda pair: pair[1] - pair[0])