[BOJ] Greedy Algorithm

문제 출처

https://blog.naver.com/kks227/220775134486

탐욕적 기법(Greedy Algorithm) (수정: 2019-11-23)

1931

https://www.acmicpc.net/problem/1931

1931번: 회의실배정

//
//  main.cpp
//  BOJ1931
//
//  Created by JSChang on 2020/08/22.
//  Copyright © 2020 JSChang. All rights reserved.
//

#include <bits/stdc++.h>

using namespace std;

struct discussion {
	int start;
	int end;
};

bool comp(discussion d1, discussion d2) {
	if(d1.end==d2.end) return d1.start < d2.start;
	else return d1.end < d2.end;
}

int main(int argc, const char * argv[]) {
	int n, cur=0, num=0;
	cin >> n;
	vector<discussion> v;
	for (int i=0; i<n; i++) {
		int x; int y; cin >> x >> y;
		discussion d;
		d.start = x; d.end = y;
		v.push_back(d);
	}
	sort(v.begin(), v.end(), comp);
	for (auto ele : v) {
		if(ele.start>=cur) {
			cur = ele.end;
			num++;
		}
	}
	cout << num << endl;
	return 0;
}

11000

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

//
//  main.cpp
//  BOJ11000
//
//  Created by JSChang on 2020/08/22.
//  Copyright © 2020 JSChang. All rights reserved.
//

#include <bits/stdc++.h>

using namespace std;

struct subject {
	int start;
	int end;
};

struct comp {
	bool operator()(subject s1, subject s2) {
		if(s1.start==s2.start) return s1.end > s2.end;
		return s1.start > s2.start;
	}
};

priority_queue<subject, vector<subject>, comp> input;
priority_queue<int, vector<int>, greater<int>> curTime;

void addRoom(subject ele) {
	if(curTime.empty()) curTime.push(ele.end);
	else {
		if(curTime.top()<=ele.start) {
			curTime.pop();
		}
		curTime.push(ele.end);
	}
}

int main(int argc, const char * argv[]) {
	int n;
	cin >> n;
	for (int i=0; i<n; i++) {
		int x; int y; cin >> x >> y;
		subject s; s.start = x; s.end = y;
		input.push(s);
	}
	while(!input.empty()) {
		addRoom(input.top());
		input.pop();
	}
	cout << curTime.size() << endl;
	return 0;
}

 

참고 자료

Vector 구조체 정렬

https://www.it-swarm.dev/ko/c++/%EA%B5%AC%EC%A1%B0%EC%B2%B4%EC%9D%98-%EB%B2%A1%ED%84%B0-%EC%A0%95%EB%A0%AC/972164260/

c++ — 구조체의 벡터 정렬

 

C++ 우선 순위 사용법

https://twpower.github.io/93-how-to-use-priority_queue-in-cpp

[C++] C++ STL priority_queue 기본 사용법과 예제

C++ 우선 순위 큐 비교 연산자

https://codingdog.tistory.com/entry/c-priority-queue-%EC%98%88%EC%A0%9C-compare-%EA%B5%AC%EC%A1%B0%EC%B2%B4%EB%A7%8C-%EC%9E%98-%EC%A0%95%EC%9D%98%ED%95%A9%EC%8B%9C%EB%8B%A4

c++ priority queue 예제 : compare 구조체만 잘 정의합시다.