Problem Link :Merge Intervals - InterviewBit
Can someone tell me that why my code is faling for this big test case.
A : [ (6037774, 6198243), (6726550, 7004541), (8842554, 10866536), (11027721, 11341296), (11972532, 14746848), (16374805, 16706396), (17557262, 20518214), (22139780, 22379559), (27212352, 28404611), (28921768, 29621583), (29823256, 32060921), (33950165, 36418956), (37225039, 37785557), (40087908, 41184444), (41922814, 45297414), (48142402, 48244133), (48622983, 50443163), (50898369, 55612831), (57030757, 58120901), (59772759, 59943999), (61141939, 64859907), (65277782, 65296274), (67497842, 68386607), (70414085, 73339545), (73896106, 75605861), (79672668, 84539434), (84821550, 86558001), (91116470, 92198054), (96147808, 98979097) ]B : (36210193, 61984219)
Logic
My Approach is 3 conditions
Note :curr indicates merged intervals . ie [1,4] +[2,3] = [1,4] (curr)
intially its value is same as given curr in argument.
1>if the interval-curr end time is less than v[i] start time then simply add the curr interval in vector and now I donot need to merge anything further and then keep adding other elements of vector coming after it.Flag=1 indicates that now I donot need to do anything ,just I have to push reming elements in array .
2>if the interval-curr start time is greater than v[i] ending time then simply just push v[i] and then continue to search .
else
{
**the intervals must be merging in this cases as above two above have failed **
so now keep them merging them in curr variable.
}
finally exit the loop and check if flag==0 (indicating I have not pushed the curr or merged interval in the vector so push it)
vector<Interval> Solution::insert(vector<Interval> &v, Interval curr)
{
vector<Interval>ans;
curr.start = min(curr.start,curr.end);
curr.end = max(curr.start,curr.end);
int flag=0;
for(long long i=0;i<v.size();i++)
{
if(curr.end < v[i].start && flag==0)
{
ans.push_back(curr);
ans.push_back(v[i]);
flag=1;
}
else if(curr.start>v[i].end)
{
ans.push_back(v[i]);
}
else
{
curr.start = min(curr.start,v[i].start);
curr.end = max(curr.end,v[i].end);
}
}
if(flag==0)
{
ans.push_back(curr);
}
return ans;
}