Merge Overlapping Intervals

Problem

You have some overlapping closed intervals and you want to merge them. What is the algorithm for this?

Solution

Here are some examples with input and output:

Input1: Intervals = [[1, 3], [2, 4], [6, 8], [9, 10]]

Output1: [[1, 4], [6, 8], [9, 10]]


Input2: Intervals = [[6, 8], [1, 9], [2, 4], [4, 7]]

Output2: [[1, 9]]

And the algorithm:

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    # Sort the array on the basis of start values of intervals.
    intervals.sort()
    stack = []
    # insert first interval into stack
    stack.append(intervals[0])
    for curr in intervals[1:]:
        # Check for overlapping interval,
        # if interval overlap
        if stack[-1][0] <= curr[0] <= stack[-1][-1]:
            stack[-1][-1] = max(stack[-1][-1], curr[-1])
        else:
            stack.append(curr)
        #
    #
    return stack

Links

• https://www.geeksforgeeks.org/merging-intervals/ (found here)

Remove duplicates from a list AND keep the original order of the elements

Problem
You have a list of elements. You want to remove the duplicates but you want to keep the original order of the elements too. Example:

input: apple, fruit, dog, fruit, cat, apple, dog, cat

output: apple, fruit, dog, cat

Solution

def remove_duplicates(li):
    my_set = set()
    res = []
    for e in li:
        if e not in my_set:
            res.append(e)
            my_set.add(e)
    #
    return res

The trick list(set(li)) is not acceptable in this case because elements are unordered in a set.

Problem Solving with Algorithms and Data Structures Using Python

Good news everyone. The book Problem Solving with Algorithms and Data Structures Using Python is available online in HTML format. This is the 2nd edition that came out in 2011.

_{amazon link}