56. Merge Intervals Leetcode Solution
Merge Intervals Leetcode Problem :
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.
Example :
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Merge Intervals Leetcode Solution :
Constraints :
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= start[i] <= end[i] <= 10^4
Example 1:
- Input: intervals = [[1,4],[4,5]]
- Output: [[1,5]]
Intuition :
We need to sort and then check the consecutive intervals. Once we find the overlapping interval. we will take the max element from it.
Approach :
- Firstly, the base case : if there are no intervals return [] .
- Sort the intervals .
- While traversing the intervals vector we will come accross two coditions
- First condition : if there is a overlapping between the intervals then just take out the max element from the ending point and thus we merged them
eg:- [1,4],[2,8] =Mergerd intervals will be> [1,8] - second condition : if there is no overlapping then simply push those interval to our resultant vector .
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
vector< vector< int>> merge(vector< vector< int>>& intervals) {
if(intervals.size()==1)
return intervals;
vector< pair< int,int>> p;
for(int i=0;i< intervals.size();i++)
{
p.push_back({intervals[i][0],intervals[i][1]});
}
sort(p.begin(),p.end());
vector< vector< int>> ans;
int f=p[0].first,s=p[0].second;
for(int i=0;i< p.size()-1;i++)
{
vector< int> a(2);
if(s>=p[i+1].first)
{
s=max(s,p[i+1].second);
}
else
{
a[0]=f;
a[1]=s;
f=p[i+1].first;
s=p[i+1].second;
ans.push_back(a);
}
}
int n=intervals.size();
ans.push_back({f,s});
return ans;
}
};
Java
class Solution {
public int[][] merge(int[][] intervals) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < intervals.length; i++) {
min = Math.min(min, intervals[i][0]);
max = Math.max(max, intervals[i][0]);
}
int[] range = new int[max - min + 1];
for (int i = 0; i < intervals.length; i++) {
range[intervals[i][0] - min] = Math.max(intervals[i][1] - min, range[intervals[i][0] - min]);
}
int start = 0, end = 0;
LinkedList< int[]> result = new LinkedList<>();
for (int i = 0; i < range.length; i++) {
if (range[i] == 0) {
continue;
}
if (i <= end) {
end = Math.max(range[i], end);
} else {
result.add(new int[] {start + min, end + min});
start = i;
end = range[i];
}
}
result.add(new int[] {start + min, end + min});
return result.toArray(new int[result.size()][]);
}
}
Python
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals = sorted(intervals, key=lambda x: x [0])
ans = []
for interval in intervals:
if not ans or ans[-1][1] < interval[0]:
ans.append(interval)
else:
ans[-1][1] = max(ans[-1][1], interval[1])
return ans
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment