CareerCup

I think this can be done with the help of a sorted list (a list of pair of integers for each interval), sorting done according to the first element of each pair.
Whenever there is a request for inserting an interval do a binary search to find the first pair such that the first integer of the pair is just smaller than the given pairs first element.

Now if the second integer of this found pair is larger than the first integer of given pair then

check if the second integer of the given pair is smaller than the second integer of the just found pair, if yes then no need to make any changes else check if the second integer of the given pair is smaller than the first element of the pair after the just found pair in the list, if yes then increase the length of the just found interval otherwise merge the found pair with the next pair.

Handle those cases where we do not find any pair in list, by either appending the given pair in front of list or at the end of the list.

// parenthesis redundancy and balancing check ((a+b)) is redundant
//algorithm is simple keep pushing numbers on stack for open bracketts,
//consecutive bracketts are numbered as same
//pop stack on encountering closed brackett symbols,
//if we encounter same numbers being popped for consecutive closed brackets
//then the string is redundant
//example ((a+b)) first open brackett will be numbered as "1" and pushed and
//same will be the number of second open brackett
//on encountering the closed brackett we pop the stack (1 will be popped)
//consecutively next brackett will also pop a value 1 which is same as previous and hence redundant.
//example (a+(b+c)) first and second brackett will be numbered as 1 and 2 resp.
// and while popping due to consecutive closed brackett we will get different values (1 & 2)



#include<stdio.h>
int stack[100],top=-1;
int pop()
{
return stack[top--];
}
void push(int x)
{
stack[++top]=x;
}
int main()
{
int temp,count,i=0,SAW_O=0,SAW_C=0,SAW_CHAR=0,pop_val=-1; //SAW_O=saw open brackett,
//SAW_C=saw closed brackett
char s[100];
scanf("%s",s);
count=1;
while(s[i]!='\0')
{
if(s[i]=='(')
{
if(SAW_O==1)
push(count);
else
{
SAW_O=1;
push(count);
}
}
else if(s[i]==')')
{
if(SAW_C)
{
temp=pop();
if(pop_val==temp){
printf("redundant %d \n",1);// cases of the type ((a+b))
return 1;
}
pop_val=temp;
i++;
continue;
}
if(SAW_O)
{
printf("redundant \n",2); // cases of the type a+b()
return 2;
}
else
{
pop_val=pop();
SAW_C=1;
}
}
else
{
if(SAW_O==1)
{
SAW_O=0;
count++;
}
SAW_C=0;
}
i++;
}
if(top>-1)
{
printf("incorrect parenthesis %d \n",3); //case when uneven number of brackets are present
return 3;
}
printf("non redundant string");
return 0;
}