白駿1931会議室手配[C+]

グレースケールアルゴリズム

この問題はグリディアルゴリズムで解くことができる.できるだけ多くの会議が重ならない問題を手配するのは、グリディアルゴリズムの間隔スケジューリング問題に相当する.

解決策

会議終了時間を早順に並べた後、並べ替え順に重ならない会議を選択して手配します.この問題では、最大何個の会議を手配することができて、会議の数を計算することができます.

sort [C++ / STL]

<algorithm>ヘッダファイルに含まれるライブラリを並べます.

template <typename T>				//함수 원형
void sort(T start, T end, Compare comp);

最後のパラメータを配置しない場合、開始から終了までの値は降順に昇順に並べられます.3番目のパラメータは、ユーザー定義の関数に基づいてソートされます.特定の値に基づいてソートできます.

sort(arr, arr+n);				//arr의 인덱스 0부터 n-1까지 정렬
sort(v.begin(), v.end());			
sort(v.begin(), v.end(), compare);              //사용자 정의 함수 사용
sort(v.begin(), v.end(), greater<자료형>());     //내림차순 
sort(v.begin(), v.end(), less<자료형>());        //오름차순 (default)

**Vectorではstart()がベクトルの先頭アドレスを返し、end()が最後のデータの後のアドレスを返します.

完全なコード(私のコード)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//끝나는 시간이 빠른 것 순서대로 배정

class Meet {
public:
	int start;
	int end;
	Meet() {
		start = 0;
		end = 0;
	}
	Meet(int start, int end) {
		this->start = start;
		this->end = end;
	}
};
bool cmp(const Meet& meet1, const Meet& meet2) {
	if (meet1.end == meet2.end) {
		return meet1.start < meet2.start;	//같을 경우 시작시간 기준으로 오름차순 정렬
	}
	else {
		return meet1.end < meet2.end;		//end를 기준으로 오름차순 정렬
	}
}

int main() {
	ios_base::sync_with_stdio(false);		//stdio 버퍼 동기화 해제
	int meeting = 0, end = 0;				//회의 수, 끝나는시간
	cin >> meeting;
	vector<Meet> meet;						//회의 저장할 벡터
	for (int i = 0; i < meeting; i++) {
		//근데 이거 왜 protedted로 하면 접근 안되는지??
		int start = 0, end = 0;
		cin >> start >> end;				//회의의 시작시간, 끝나는 시간 입력
		Meet m(start, end);					//회의 객체 생성
		meet.push_back(m);					//벡터에 추가
	}
	sort(meet.begin(), meet.end(), cmp);		//끝나는 시간이 빠른 순서대로 정렬 

	int cnt = 1, idx = 1;
	end = meet[0].end;					//배정된 회의의 끝나는 시간.
	while (idx < meeting) {
		if (end <= meet[idx].start) {	//배정된 회의의 끝나는 시간이 현재 순회중인 인덱스의 시작하는 시간보다 작거나 같으면 현재 회의 배정
			end = meet[idx].end;
			cnt++;
		}
		idx++;
	}
	cout << cnt;		//최종 배정된 회의 수 출력

	return 0;
}

他者コード

vector<pair<type, type>>		//선언
make_pair(value, value)			//값 할당 

first(最初のパラメータ値)、second(2番目のパラメータ値)を使用して、2つのパラメータにアクセスできます.関連する2つの値では、主に各条件に基づいて値をソートするために使用されます.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;


int main()
{
	int N, end, begin;

	vector<pair<int, int>> schedule;

	cin >> N ;

	for (int i = 0; i < N; i++)
	{
		cin >> begin >> end;
		schedule.push_back(make_pair(end, begin));
	}
	
	sort(schedule.begin(), schedule.end());
	
	int time = schedule[0].first;
	int count = 1;
	for (int i = 1 ;i < N; i++) 
	{
		if (time <= schedule[i].second )
		{
			count++;
			time = schedule[i].first;
		}
	}

	cout << count;
}

パフォーマンスの違い

下のコードは私のコードで、上のコードはpairのコードを使って、時間の差は3倍ぐらいです.私から見ればpairのコードを使うほうが効率的なようですが、原因は分かりません.後で知ったら使いましょう.