Python Program to Merge Intervals
Merge Intervals
On this page we will learn to create a Python Program to Merge Intervals.
In this problem we have to merge all possible overlapping intervals and print them.
- Input : [ [1, 3], [2, 6], [8, 10], [15, 18], [18, 20] ]
- Output : [ [1, 6], [8, 10], [15, 20] ]
- Explanation : In this [1,3] and [2,6] are overlapping so we’ll merge then and replace with [1,6]. [8,10] will remain same as it is not overlapping with any interval. Again as we can see [15,18] is overlapping with [18,20] there for it will be replaced by [15,20].
Algorithm
- Start
- Sort the given array in Ascending order
- Initialize a variable i with value zero
- Run a loop while i less then l – 1 (length of array – 1)
- For each iteration check if starting point or ending point of any two consecutive intervals is same then increment the value of i by 1, skip for this iteration with keyword (continue)
- Initialize an empty array a
- Use a for loop to iterate from arr[i][0] to 1 + arr[i+1][1] and for each iteration append it to a
- Use a for loop to iterate between arr[i][0] to 1 + arr[i+1][1] using variable n
- If the variable n is in array a then initialize a list name new_pair having value minimum of arr[i][0] and arr[i+1][0] to index zero , maximum of arr[i][1] and arr[i+1][1] at index one
- Assign the value of new_pair to arr[i] and arr[i+1] both
- Set the value of i to zero and break the for loop
- Increment the value of i by 1
- Create a new array ans and append all the distinct element of arr to ans
- Print ans
Python Code
Run
def merge(arr, l):
arr.sort()
i = 0
while i < l - 1:
if arr[i][0] == arr[i + 1][0] and arr[i][1] == arr[i + 1][1]:
i += 1
continue
a = []
for n in range(arr[i][0], 1 + arr[i][1]):
a.append(n)
for n in range(arr[i + 1][0], 1 + arr[i + 1][1]):
if n in a:
new_pair = [min(arr[i][0], arr[i + 1][0]), max(arr[i][1], arr[i + 1][1])]
arr[i] = new_pair
arr[i + 1] = new_pair
i = 0
break
i += 1
ans = []
for i in arr:
if i not in ans:
ans.append(i)
return ans
arr = [[1, 3], [2, 6], [8, 10], [15, 18], [18, 20]]
l = len(arr)
print(merge(arr, l))
Output :
[ [1, 6], [8, 10], [15, 20] ]
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
If you want to practice similar Questions click on given button.
Login/Signup to comment
Thank me later –
def interval(arr):
arr.sort(key=lambda i:i[0])
output=[arr[0]]
for start,end in arr[1:]:
last_end=output[-1][1]
if start<= last_end:
output[-1][1]=max(last_end,end)
else:
output.append([start,end])
return output
arr=[ [1, 3], [2, 6], [8, 10], [15, 18], [18, 20] ]
print(interval(arr))
Hey there,
Thanks for answering, Kindly join our Discord server for any technical related queries.
arr = [ [1, 3], [2, 6], [8, 10], [15, 18], [18, 20] ]
i = 0
while i = arr[i+1][0]:
res = [arr[i][0] , arr[i+1][1]]
arr.pop(i)
arr.pop(i)
arr.insert(i,res)
else:
i = i + 1
print(arr)
after while add if arr[i][1] >= arr[i+1][0]:
Hey there,
Thanks for answering, Kindly join our Discord server for any technical related queries.
Hey there,
Thanks for answering, Kindly join our Discord server for any technical related queries.