Algorithm to merge overlapping intervals found in a list. Python Solution

Entry 3

Algorithm questions often come in various forms and this was one that came with a lot of confusion at first. My goal in writing this article is to provide my solution to solving this problem and to also show off my new found love in learning python and all of its dirtiness and sexiness. Don't mind me, straight to the point.

What's does an interval mean with regards to this problem?

An interval is an array that has a start and end value, e.g
interval1 = [4,6]
The start value is always lesser than the end value, so
[4,6] is valid but [5,2] is invalid.

So what is an overlapping interval?

An overlapping interval is a collection of intervals, whose previous interval contains an end value that is greater than or equal to the start value of the next interval in the collection.

Psst, I'm sorry if that confused you, but here's a code example

intervalCollection1 = [[1, 3], [2, 6], [8, 10], [15, 18]]
intervalCollection2 = [[1,4],[4,5]]

intervalCollection1 has at index 1 a start value that's less than the end value at index 0. intervalCollection2 also has at index 1 a start value that's equal to the end value of index 0.

Quick Note:

Before we proceed, one thing you must take note of when dealing with the values in nested arrays, changing the value of any item at an index also changes the value in the collection. This is because the intervals in the collections are stored not by value but by reference.

Test this out and see for yourself.

one = [1,2]
two = [one, [3,4]]

print("before changing one's values")
print(one,"two -> ", two)

one[0] = 21
one[1] = 22

print("after changing one's values")
print(one, "two -> ", two)

So onto the algorithm mate 🏴‍☠️☠️

• First check that the collection's length is greater than 1, if it isn't return the collection.
• Sort the collection of intervals
• Store the current interval in a variable say a_var
• Create a new collection to hold the values and add a_var into it.
• Loop through the collection and store the next interval start and end values in two variables
• Store the end value of a_var in a variable
• Check that the end value of the a_var variable is greater than or equal to the start value of the next interval
• if true, change the end value of the a_var to be the max of the current end interval
• else change the value held in the a_var variable to be current iterate
• push the a_var variable into the collection created.
• Return the new collection created

CODE

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) <= 1:
            return intervals
        output = []
        intervals.sort();


        current = intervals[0]
        output.append(current)



        for i in range(len(intervals)):
            current2 = current[1];
            next1 = intervals[i][0]
            next2 = intervals[i][1]

            if current2 >= next1:
                current[1] = max(current2, next2)
            else:
                current = intervals[i]
                output.append(current)

        return output

Conclusion

What I've discovered with solving algorithm questions is that there's always something new to learn. With this question, it was learning what an interval array is and hopefully, when I see such questions or it's variations in an interview or during tasks assigned to me, I am confident enough to solve the challenge and of course, conquer it. A little birdy also told me this question has come up at an Uber interview, you never know when this might come in handy.