# https://www.codechef.com/AM19MOS/problems/COLINT

#include
#include
#include
using namespace std;

vector<pair<pair<int, int>, int> > intervals;

int T, n, L, R;
int color[100010];

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>T;
while(T–)
{
cin>>n;
intervals.clear();
for(int i = 0; i < n; ++i)
{
cin>>L>>R;
intervals.push_back(make_pair(make_pair(L, R), i));
}
sort(intervals.begin(), intervals.end());
int max_e0 = 0;
int max_e1 = 0;

``````    for(auto p : intervals)
{
int s = p.first.first;
int e = p.first.second;
int label = p.second;
if(max_e0 >= max_e1)
{
color[label] = 1;
max_e1 = max(max_e1, e);
}
else
{
color[label] = 0;
max_e0 = max(max_e0, e);
}
}
for(int i = 0; i < n; ++i)
cout<<color[i];
cout<<endl;
}
``````

}
/*

after challenge end
i tried to understand some of problem by looking at
soln of others but i am not able to understand what logic they have used
same goes to many problems!
*/

Here i made a detailed explanation of my solution. You may take a look.

Let’s say we color first interval with blue, then afterwards if blue color is colored till x and yellow is colored till y. Now if x > y, in this case we should color the current interval with yellow so that this part can have both colors. And if x < y then we should color the current interval with blue with same reasoning. if x=y, in this case we can use any color. So simply manage 2 arrays one for blue and one for yellow which stores maximum range till which blue and yellow are colored currently. And based on that pick the current color whose range is less.

2 Likes

Lol, i was trying to explain that in simple words . But failed in it.
And you did it.

This was the idea we got while participating onsite. So i thought to share it here. It’s pretty easy that way.

2 Likes

Thanks for replying soon and help, nice explanation

How u catch that logic, tried for 2 hours still not able solve
Thanks for help

Scrambling on my paper