fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. struct node
  8. {
  9. 	int x,y,index;
  10. 	node(int x1,int y1,int index1)
  11. 	{
  12. 		x=x1;
  13. 		y=y1;
  14. 		index=index1;
  15. 	}
  16. };
  17.  
  18. class comp
  19. {
  20. 	public:
  21. 	bool operator()(node*a,node*b)
  22. 	{
  23. 		return a->y > b->y;
  24. 	}
  25. };
  26.  
  27. bool comp2(node*a,node*b)
  28. {
  29. 	if(a->x == b->x)
  30. 	{
  31. 		return a->y < b->y;
  32. 	}
  33. 	else
  34. 	{
  35. 		return a->x < b->x;
  36. 	}
  37. }
  38.  
  39.  
  40. int main() {
  41.  
  42. 	int n;
  43. 	cin>>n;
  44.  
  45. 	int ans[n]={0};
  46. 	vector<node*> V;
  47. 	for(int i=0;i<n;i++)
  48. 	{
  49. 		int x,y;
  50. 		cin>>x>>y;
  51. 		V.push_back(new node(x,y,i));
  52. 	}
  53.  
  54. 	priority_queue<node*,vector<node*>,comp> PQ;
  55.  
  56. 	sort(V.begin(),V.end(),comp2);
  57.  
  58. 	int roomCnt=0;
  59. 	int maxCnt=0;
  60. 	for(int i=0;i<n;i++)
  61. 	{
  62. 		if(PQ.empty() || PQ.top()->y >= V[i]->x)
  63. 		{
  64. 			roomCnt++;
  65. 			ans[V[i]->index]=roomCnt;
  66. 			PQ.push(new node(V[i]->x,V[i]->y,roomCnt));
  67. 			if(maxCnt < roomCnt)
  68. 			{
  69. 				maxCnt = roomCnt;
  70. 			}
  71. 		}
  72. 		else
  73. 		{
  74. 			node*vacant = PQ.top();
  75. 			PQ.pop();
  76. 			PQ.push(new node(V[i]->x,V[i]->y,vacant->index));
  77. 			ans[V[i]->index]=vacant->index;
  78. 		}
  79. 	}
  80.  
  81. 	cout<<maxCnt<<endl;
  82. 	for(int i=0;i<n;i++)
  83. 	{
  84. 		cout<<ans[i]<<" ";
  85. 	}
  86. 	cout<<endl;
  87.  
  88. 	return 0;
  89. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
3
1 2
2 4
4 4
stdout
copy 
2
1 2 1
https://ideone.com/fZNpSr
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!