To merge overlapping intervals in Python

     Merging means combining. Basically, it is a technique to merge overlapping intervals to non-overlapping intervals.

What is an interval?

              An interval is a range between two data. The data may be a time, memory and so on.

Eg:

[1,4] means in the range from 1 to 4.

[3,5] overlaps with [1,4]. Here, 3 is in the range.

What is overlapping?

              When two ranges have same time. It may overlap.

To avoid this, merging intervals are used.

Logic:

To merge the intervals, use this logic.

• First, sort the intervals by using their start time.
• For each interval, iterate it.
• Let us compare the current interval and last merged. If they overlap, combine them into a single unit.
• Else, just add the current interval as it is.

Python implementation:

The python program is given below.

def merge_intervalsEg(intervals):

    # Step 1: let us Sort intervals by using start time

    intervals.sort(key=lambda x: x[0])

        merged = []

    # iterating each interval

    for interval in intervals:

        # If the merged interval is empty or no overlap, add the interval

        if not merged or merged[-1][1] < interval[0]:

            merged.append(interval)

        else:

            # if Overlap exists, merge it with the last interval

            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

def main():

    # Sample input

    intervals = [[2, 4], [1, 6], [7, 9], [12, 18]]

    print("The Original intervals are:", intervals)

    result = merge_intervalsEg(intervals)

    print("The Merged intervals are:", result)

# Entry point

if __name__ == "__main__":

    main()

Output:

To get the output, use the below code.

C:\raji\blog>py mergedintereg.py

The Original intervals are: [[2, 4], [1, 6], [7, 9], [12, 18]]

The Merged intervals are: [[1, 6], [7, 9], [12, 18]]

The implementation of merging intervals in python was written and executed successfully. Hope, this code is easy to understand. Keep coding!!!