koi_cha/곽병학

No difference found

#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

bool chain(pair<int, int> &p1, pair<int, int> &p2) {
	if(
	(p1.first > p2.first && p1.second < p2.second) ||
	(p1.first == p2.first && p1.second < p2.second) ||
	(p1.first > p2.first && p1.second == p2.second)
	) return true;

	if(
	(p1.first < p2.first && p1.second > p2.second) ||
	(p1.first == p2.first && p1.second > p2.second) ||
	(p1.first < p2.first && p1.second == p2.second)
	) return true;

	return false;
}

class op {
public:
	bool operator() (pair<int, int> &p1, pair<int, int> &p2) {
		if(p1.first != p2.first)
			return p1.first < p2.first;
		else
			return p1.second > p2.second;
	}
}myOp;

int main() {
	vector<pair<int,int>> vc;
	vector<int> vd;
	vc.push_back(make_pair(0,0));
	vd.push_back(0);
	
	int t, dummy, s, e;
	cin>>t;
	while(t--) {
		cin>>dummy>>s>>e;
		vc.push_back(make_pair(s,e));
	}
	
	vd.resize(vc.size());
	for(int i=1; i<vd.size(); i++) 
		vd[i] =1;

	sort(vc.begin() +1 , vc.end(), myOp);

	for(int i=2; i<vc.size(); i++) {
		for(int j=i-1; j>0; j--) {
			if(chain(vc[i], vc[j])) {
				vd[i] = vd[j] +1;
				break;
			}
		}
	}

	int max = vd[1];
	for(int i=2; i<vd.size(); i++)
		if(max < vd[i]) max = vd[i];

	cout<<max<<endl;
	return 0;
}