[C/C++ : JUNGOL] 1828번 : 냉장고

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=3050 

JUNGOL

 

 

1. 최소의 냉장고를 구하기 위해서는 겹치는 구간을 활용한다.

2. 1번의 겹치는 구간을 활용하기 위해서는 정렬이 필요한데, 가장 높은 온도를 기준으로 정렬한다.

3. 겹치는 구간을 초기화하면서 겹치는 구간이 있을 때는 가장 낮은 온도, 가장 높은 온도의 범위를 줄여나가며 초기화하고 겹치는 구간이 없다면 냉장고가 하나 더 필요하다. 이 때의 온도로 또 초기화해주는 방법으로 구현하였다.

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
vector<pair<int,int>> ps;

bool cmp(pair<int, int> lhs, pair<int, int> rhs) {
	if (lhs.second == rhs.second) return lhs.first < rhs.first;
	return lhs.second < rhs.second;
}

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b;
		ps.push_back({ a, b });
	}
}

bool isValid(int start, int end, int x1, int x2) {
	if (x1 < start && x2 < start) return false;
	if (end < x1 && end < x2) return false;
	return true;
}

int solution() {
	int answer = 0;
	int start = -271, end = -271;
	sort(ps.begin(), ps.end(), cmp);	

	for (auto t : ps) {
		if (isValid(start, end, t.first, t.second)) {
			start = max(start, t.first);
			end = min(end, t.second);
		}
		else {
			answer++;
			start = t.first, end = t.second;
		}
	}

	return answer;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}