[EPPER/15회 7번] 도서관 좌석 예약(중-4)

//프로그래머스에서는 main함수 및 입출력문이 필요하지 않습니다. 대신 solution함수만 작성하면 됩니다.
#include <iostream>
#include <vector>
#include <algorithm>

/*
Greedy Algorithm

"종료시간"이 빠른 순서대로 2자리를 아무곳이나 배치 
하지만 종료시간이 동일하다면 시작시간이 더 빠른 것을 먼저 배치 


sort(T start, T end, Compare comp);

sort(정렬 시작,정렬의 끝, 기준함수)

start<= 범위 <end 로 정렬하기 때문에 주의하기! (마지막 포함아님 )

Compare comp? 
오름차순으로 만들 것인가 내림 차순으로 만들 것인가? 를 결정할 수 있음 
(a,b) 순서대로 매개변수가 들어왔을 때 
a를 기준으로 함 
a가 b에 비해 크다 (a>b) -> 내림차순
a가 b에 비해 작다 (a<b) -> 오름차순



*/

using namespace std;

//시작시간 배열(s) , 끝나는 시간 배열(e)를 세트로 묶은 pair vector
vector<pair<int,int>> v;

//sort 함수를 사용할 때 기준이 되게 하는 함수 
bool compare(pair<int,int>a, pair<int,int>b){
	
	//first :  시작 예약 시간 , second : 끝나는 시간 
	if(a.second == b.second) // 만약 끝나는 시간이 둘이 같은경우 시작 시간이 이른 것이 앞으로 
		return a.first < b.first; //참이면 1, 거짓이면 0 -> 1이면 (작은걸)a를 앞으로 (오름차순)
	else//다른 경우 끝나는 시간이 빠른게 앞으로 
		return a.second < b.second; //참이면 1, 거짓이면 0 -> 1이면 a를 앞으로 (오름차순)

}

int solution(vector<int> s, vector<int> e,int n){
	int answer = 0;
	
	//2개의 좌석 -> 각각 이용이 끝나는 시간을 저장함(각 학생의 퇴실시간(?))
	int e1 = -1;
	int e2 = -1; 
	
	//s와 e 배열을 하나의 pair로 만들기 
	 for (int i=0; i<n; i++){
		 v.push_back({s[i],e[i]});
	 }
	
	//끝나는 순서대로 정렬 
	sort(v.begin(),v.end(),compare);
	
	//배치
	for(int i=0; i<n; i++){
		
		if(e1<=v[i].first){ //해당 좌석의 끝나는 시간이 예약자의 시작 시간보다 작은경우 ->이용가능
			answer++;
			e1 = v[i].second; // 끝나는 시간으로 갱신 
		}
		else if(e2<=v[i].first){ //좌석1은 이용불가능이고, 2는 이용가능함 
			
			//코드에서 항상 1번을 먼저 고려하기 때문에 1번자리 학생을 2번으로 보내고 
			// 2번자리에 할당될 학생을 1번 자리에 배정함 
			e2 = e1; // 1번에 앉았던 애를 2번으로 옮김 
			e1 = v[i].second; //지금 현재 앉힐 학생을 1번에 배정 
			
			
			answer++;
		}
	}
	
	return answer;
	
}


int main() {	
	//배열
	vector<int> s;
	vector<int> e;
	int n;
	int min;
	
	cin>>n;
	
	for(int i=0;i<n;i++){
		cin>>min;
		s.push_back(min);
	}
	for(int i=0;i<n;i++){
		cin>>min;
		e.push_back(min);
	}

	cout<< solution(s,e,n);
	
	
	return 0;
}