56. Merge Intervals | LeetCode Medium | Python Solution | Sorting, Array, Interval

Опубликовано: 24 Ноябрь 2022
на канале: Shaheer Shukur

385

Leetcode medium problem 56. Merge Intervals, detailed explanation and solution in python language.

LeetCode Problem Link: https://leetcode.com/problems/merge-i...
Solution (Python Code): https://github.com/shaheershukur/Leet...

#leetcode #python #solution

Problem Statement:
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given and array of intervals, and we need to check whether there are any overlapping intervals and merge them together.
each interval will have a starting number and an ending number. so we can actually represent it on a number line.

the first scenario is, the two intervals are completely disjoint.
in this case, we don't have to do anything, we will have both the intervals in the output.

the second scenario is, the two intervals are touching each other.
in this case, as per the problem statement, we can merge them together to form a single interval.
when we are creating the new interval, the starting number will be the minimum of the two starting numbers, and the ending number will be the maximum of two ending numbers.
this new interval will be added to the output.

the third scenario is, the two intervals are overlapping to some extend.
in this case, we can merge them together to form a single interval.

the fourth scenario is, one interval is completely overlapped by the other interval.
in this case also, we can merge them together to form a single interval.

so based on these observations, lets solve this problem with the help of an example.
here we are having a problem. the intervals are scattered across the number line.
so there can be a chance of encountering an interval which was supposed to occur before the current interval.
for example, here we have interval [1, 2] at index 2. so only after reaching index 2, we can check whether this interval is overlapping with any of the previously analyzed intervals.

we can fix this problem by sorting the given array of intervals based on the starting number.
after sorting, the number line will be like this.
now, we only need to check whether the current interval can be merged with the previously analyzed interval.
so we can easily merge the intervals in a single go, moving in the forward direction.

here, for the first interval, we don't have a previous interval in the output array.
so we can add it to the output array without any check.

for the second interval [3, 5], the previously analyzed interval is the last interval present in the output array. i.e., [1, 2].
here we will check whether the interval [3, 5] can be merged with the interval [1, 2].
for that we can check whether the starting number 3 of interval [3, 5] is falling on or before the ending number 2 of the last interval [1, 2].
since 3 is greater than 2, we cannot merge this interval with the last interval.
so we can add it to the output array without any check.

for the third interval [4, 6], the last interval present in the output array is [3, 5].
here the starting number 4 of the interval [4, 6] falls before the ending number 5 of the interval [3, 5].
that means, this interval can be merged with the last interval present in the output array.

since the input array was already sorted in the beginning, we know that the last interval in the output array will be having the minimum starting number compared to the current interval we are analyzing.
so we only need to check which interval is having the maximum ending number.
and we will be updating the last intervals ending number with that maximum number.
so, as a whole, we have a new merged interval in the output array.

for the fourth interval [6, 7], the last interval present in the output array is [3, 6].
here the starting number 6 of the interval [6, 7] is equal to the ending number 6 of the interval [3, 6].
that means, this interval can be merged with the last interval present in the output array.
we will update the last intervals ending number with the maximum number 7.
so now we have a new merged interval in the output array.

in the end, this is the result we have.
now, lets code the solution.

first, we will sort the intervals based on the starting number.

we will create a new array for storing the new intervals.
and at last we will be returning it.

we can store the first interval in the output array, so that we need not have to put any conditional checks for empty array during the iteration.