Pagini recente » Cod sursa (job #2105526) | Cod sursa (job #1058362) | Cod sursa (job #2729596) | Cod sursa (job #2296677) | Cod sursa (job #2055348)
#include<fstream>
#include<algorithm>
#include<iostream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("data.in");
ofstream g("data.out");
struct interval
{
int left,right;
int grupa;
bool operator >(const interval& a) const
{
return right>a.right;
}
};
bool cmp(interval a, interval b)
{
return a.left<b.left;
}
int main()
{
int n;
f>>n;
interval lista[n+1];
for(int i=0;i<n;++i)
{
f>>lista[i].left>>lista[i].right;
}
sort(lista,lista+n,cmp);
vector <interval> multimi[n+1];
int m=0;
priority_queue <interval(), vector<interval> , greater<interval> > q;
++m;
lista[0].grupa=m;
multimi[m].push_back(lista[0]);
q.push(lista[0]);
for(int i=1;i<n;++i)
{
if(q.top().right>lista[i].left)
{
++m;
lista[i].grupa=m;
multimi[m].push_back(lista[i]);
q.push(lista[i]);
}
else
{
lista[i].grupa=q.top().grupa;
multimi[q.top().grupa].push_back(lista[i]);
q.pop();
q.push(lista[i]);
}
}
g<<m<<"\n";
for(int i=1;i<=m;++i)
{
g<<"Multimea "<<i<<": ";
for(unsigned int j=0;j<multimi[i].size();++j)
g<<"("<<multimi[i][j].left<<","<<multimi[i][j].right<<"); ";
g<<"\n";
}
return 0;
}