A long, long time ago... clear solution for Merge Intervals (iterator version) by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

A long, long time ago... solution in Clear category for Merge Intervals (iterator version) by veky

def merge_intervals(intervals):
    it = iter(intervals)
    a, b = next(it, (None, None))
    if a is not None:
        for c, d in it:
            if c - b >= 2:
                yield a, b
                a, b = c, d
            elif b < d:
                b = d
        yield a, b

Aug. 28, 2018

Comments:

Wartem on Sept. 13, 2022, 8:49 a.m.
Awesome. Without converting to a sequential data structure and then converting back with iter(). I guess it's called "(iterator version)" for a reason. Thanks!

veky on Sept. 13, 2022, 10:45 a.m.
Yes, it's a bit of a challenge, but really rewarding to figure out a way to do this in time instead of in space. :-)

amandel on Oct. 3, 2022, 6:15 p.m.
It assumes that the intervals are ordered by leftmost end, even though this was not specified.

veky on Oct. 5, 2022, 4:03 a.m.
As said, it was long time ago, I think it was originally written in Py2 even. But an important point is that if you really want to embrace the iterator strategy, then the only way the task would make sense if the input was also an iterator is that they'd be ordered. Otherwise you can't even output a single interval back until you read all the input, and there might be infinitely many. Yes, here it is "solved" by having an input be a sequence, but really, then it is just a "half-iterator version". :-]

amandel on Oct. 5, 2022, 10:27 a.m.
You are right, of course. I recently got an invite for the mission, and solved it with code not significantly different from yours. After passing the tests, I stepped back, and realized that I was making an unstated assumption, so I rewrote the code to an ugly one that starts by sorting the data. The statement of the mission should be fixed with the added assumption, but I don't think it will be :-)

Different kind of sets

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!