백준 1931번 : 회의실 배정

문제 링크 : www.acmicpc.net/problem/1931

내 풀이(2021.1.9.) :

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

deque<pair<int,int>> dq;

bool comp(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) return a.first < b.first;
	else return a.second < b.second;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; cin >> N;

	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b;
		dq.push_back(make_pair(a, b));
	}
	sort(dq.begin(), dq.end(), comp);

	int cnt = 0;
	int next = dq.front().second;
	dq.pop_front();	cnt++;

	while (!dq.empty()) {
		if (dq.front().first < next) dq.pop_front();
		else {
			next = dq.front().second;
			dq.pop_front();	cnt++;
		}
	}

	cout << cnt;

	return 0;
}

 

* sort 시 비교 함수의 customizing

 - bool 타입 리턴

 - a -> b 순서로 정렬하고 싶으면 return a < b 또는 a - b < 0

sort(dq.begin(), dq.end(), comp);

bool comp(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) return a.first < b.first;
	else return a.second < b.second;
}

 

* deque의 시간 복잡도

 - at() : O(1)

 - push_front : amortized O(1)

 - push_back : amortized O(1)

 - pop_front : amortized O(1)

 - pop_back : amortized O(1)

 - insert : O(n)

 - erase : O(n)

 

* vector의 시간 복잡도

 - at() : O(1)

 - push_back : amortized O(1)

 - pop_back : amortized O(1)

 - insert : O(n)

 - erase : O(n)

 

참고 : stackoverflow.com/questions/22306949/does-deque-provide-o1-complexity-when-inserting-on-top