Problem:
Given a set of non overlapping intervals
Example 1: (1,4) (6,10) (14, 19) and another interval (13, 17) merge them as (1,4) (6,10) (13,19)
Example 2: (1,5) (6, 15) (20, 21) (23, 26) (27, 30) (35, 40)
New interval (14, 33)
Output should be
(1,5) (6, 33) (35, 40)
This is because the new interval overlaps with (6, 15) (20, 21) (23, 26) (27, 30)
Input:
The first line contains a number T, the number of test cases.
The next line contains an integer N, which is the number of non-overlapping intervals.
The next N lines contain two space separated integers which denote the start and end points of an interval. This is followed by a blank line.
The next line contains two space separated integers which denote the new interval.
Output:
The output for each test case should contain a line of the form “Case #X: “ where X is the number of the test case.
The next lines should contain the merged intervals in the ascending order.
C++ Code:
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int A[100],B[100],t,a,b,n,d=1;
cin>>t;
while(t--)
{
int m=1;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>A[i];
cin>>B[i];
}
sort(A,A+n);
sort(B,B+n);
cin>>a>>b;
int j=0;
while(j<=n-1 && a>A[j] && a>B[j])
{
j++;
}
int k=n-1;
while(k>=0 && b<B[k] && b<A[k])
{
k--;
}
if(j<k)
{
if(a<A[j])
{
A[j]=a;
}
if(b>B[k])
{
B[j]=b;
}
else
{
B[j]=B[k];
}
}
else if(j>k)
{
m=0;
}
else
{
if(B[j]<b)
{
B[j]=b;
}
}
if(m==1)
{
cout<<"Case #"<<d<<": "<<endl;
for(int i=0;i<=j;i++)
{
cout<<A[i]<<" "<<B[i]<<endl;
}
for(int i=k+1;i<n;i++)
{
cout<<A[i]<<" "<<B[i]<<endl;
}
}
else
{
cout<<"Case #"<<d<<": "<<endl;
for(int i=0;i<j;i++)
{
cout<<A[i]<<" "<<B[i]<<endl;
}
cout<<a<<" "<<b<<endl;
for(int i=k+1;i<n;i++)
{
cout<<A[i]<<" "<<B[i]<<endl;
}
}
d++;
}
return 0;
}
Sample Input:
1
6
1 5
6 15
20 21
23 26
27 30
35 40
14 33
Sample Output:
Case #1:
1 5
6 33
35 40
