qstn:-
My WA solution
http://www.codechef.com/viewsolution/6272595
My algorithm
1)Handle each compartment separately
2)find the maximum number of disjoint set possible for each compartment
How i handled the code
1)as number of compartment is large 10^9 i use map to mark each compartment separately(some
compartment is not used)
eg: there are three compartment only with number 10^8,10^9,10^7
then 10^6==>0
10^7==>1
10^8==>2
2)sort the range of time according to end time for each compartment seprately
3)two range are possible if v[i-1].end_time<=v[i].start_time
lli m1=v[i][0].e;
lli z=1;
for(lli j=1;j< v[i].size();j++)
{
if(m1<=v[i][j].s)
{
z++;
}
m1=v[i][j].e;
}
note:-some code line are explained here
if(comp>k)//if demanded compartment is greater than k thn no allocation as data is useless
continue;
- here mapping as mentioned above
if(p==m.end())
{
m.insert(pair<lli,lli>(comp,z));
v[z].clear();
x=z;
z++;
}
else
{
x=p->second;
}
v[x].push_back(temp);
can you point where i am doing wrong or my whole algorithm is wrong.
thank you