when I saw this question, there was in my mind that it is saying to insert, ofcourse it will be inplace and end up doing inplace which beats 5% people in runtime😂 BUT beats 98% people in terms of Memory Here is the code, if anyone wanna see this approach class Solution { public: vector insert(vector& inter, vector& newinter) { int n=inter.size(),low=0,high=n-1,ans=-11; while(low
small recomendations in the code: 1. use different variables to find the starting and ending ranges for intersection values 2. use a = in the 2nd while to take in the range when the newInterval[1] matches the intervals[i][1] in any case, for eg: newInterval={4,8} and the one of the intervals is [.......{8,10},.....] code: vector insert(vector& intervals, vector& newInterval) { vectorans; int i=0; while(i
for java class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { ArrayList ans = new ArrayList(); int start= 0; int end= 1; int n = intervals.length; int i = 0; //left part which do not have overlap while(i
Here is the smaller code: class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { int n = intervals.length; List ans = new LinkedList(); int i =0; while(i
This could have been done with binary search as well. Thats the point of this question otherwise what's the difference in this question and merge intervals. Could have just added the new interval into the old and applied merge intervals ?
May be you can identify where to insert newInterval into given intervals using binary search after that you can use merge interval problem solution.(No need to sort in merge interval problem solution) Time complexity:O(logn) + O(n).
while(i
CORRECTION : In the 2nd while loop initialization it will be while(i < n && intervals[i][0]
when I saw this question, there was in my mind that it is saying to insert, ofcourse it will be inplace and end up doing inplace which beats 5% people in runtime😂 BUT beats 98% people in terms of Memory
Here is the code, if anyone wanna see this approach
class Solution {
public:
vector insert(vector& inter, vector& newinter) {
int n=inter.size(),low=0,high=n-1,ans=-11;
while(low
small recomendations in the code:
1. use different variables to find the starting and ending ranges for intersection values
2. use a = in the 2nd while to take in the range when the newInterval[1] matches the intervals[i][1] in any case, for eg: newInterval={4,8} and the one of the intervals is [.......{8,10},.....]
code:
vector insert(vector& intervals, vector& newInterval) {
vectorans;
int i=0;
while(i
It would give wrong output. Inside the second while loop condition should be i
for java
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
ArrayList ans = new ArrayList();
int start= 0;
int end= 1;
int n = intervals.length;
int i = 0;
//left part which do not have overlap
while(i
Here is the smaller code:
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int n = intervals.length;
List ans = new LinkedList();
int i =0;
while(i
class Solution {
public:
vector insert(vector& intervals, vector& newInterval) {
int n = intervals.size();
int i = 0;
vectorresult;
while(i
CPP
class Solution {
public:
vector insertNewEvent(int n, vector &intervals, vector &newEvent)
{
vector ans;
int i = 0;
while(i < n && intervals[i][1] < newEvent[0])
{
ans.push_back(intervals[i]);
i++;
}
// int start = -1
while(i < n && intervals[i][0] newEvent[1])
{
ans.push_back(intervals[i]);
i++;
}
return ans;
}
};
super simple code
class Solution {
public:
vector insert(vector& intervals, vector& newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(),intervals.end());
int n=intervals.size();
vectorans;
for(int i=0;ians.back()[1])
ans.push_back(intervals[i]);
else
ans.back()[1]=max(ans.back()[1],intervals[i][1]);
}
return ans;
}
};
Sir please start making videos on strings and stacks
tysm sir
thank you
in the last question (1,2) & (2,3) were not considered as overlapping but in this one it will considered, how can we be sure ?
Understood
nice
This could have been done with binary search as well.
Thats the point of this question otherwise what's the difference in this question and merge intervals.
Could have just added the new interval into the old and applied merge intervals ?
phenomenal playlist
watched
very well explained playlist
super simple
class Solution {
public:
vector insert(vector& intervals, vector& newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(),intervals.end());
int n=intervals.size();
vectorans;
for(int i=0;ians.back()[1])
ans.push_back(intervals[i]);
else
ans.back()[1]=max(ans.back()[1],intervals[i][1]);
}
return ans;
}
};
given intervals are already sorted, use it rather than sorting it again and converting this question into merge intervals!
@@anubhav0355Look carefully this is converted into merge interval question
this is an nlogn approach, will give TLE, we need O(n). And yeah as it is already sorted we shouldn't sort again
@@psinity However it is accepted
May be you can identify where to insert newInterval into given intervals using binary search after that you can use merge interval problem solution.(No need to sort in merge interval problem solution)
Time complexity:O(logn) + O(n).