U E D R , A S I H C RSS

1R/2016_09_26 (rev. 1.3)

1R/2016_09_26



1. 오늘의 문제

2. 참가자

  • 15이원준
  • 박인서

3. 코드

3.1. 15이원준

#include<iostream>
#include<map>
#include<utility>
using namespace std;

int main(){
  int N, ans = 0;
  multimap<int, int, less<int>> arr;
  cin>> N;

  for(int i = 0; i<N; i++){
    int tmp1, tmp2;
    scanf("%d %d", &tmp1, &tmp2);
    arr.insert(pair<int, int>(tmp1, tmp2));
  }

  for(auto it = arr.begin(); it != arr.end();){
    int firstfinish = it->second;

    for(it++; it != arr.end() && it->first < firstfinish; it++){
      int etime = it->second;
      if(etime < firstfinish){
        firstfinish = etime;
      }
    }
    ans++;
  }

  cout<< ans << endl;
}

3.2. 박인서

#include <iostream>
#include <vector>
#include <algorithm>
typedef std::pair<int, int> pair_int;
std::vector<pair_int> meet;

int main()
{
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		int t1, t2;
		std::cin >> t1 >> t2;
		meet.push_back(pair_int(t1, t2));
	}

	std::sort(meet.begin(), meet.end(), [](pair_int t1, pair_int t2){
		return (t1.second == t2.second ? t1.first < t2.first: t1.second < t2.second); });
	int time = 0, cnt = 0;
	for (int i = 0; i < n; i++) {
		if (meet[i].first < time) continue;
		time = meet[i].second;
		cnt++;
	}

	std::cout << cnt;
	return 0;
}

3.3. 곽정흠


4. 아이디어

4.1. 15이원준

  • 겹치는 시간 중에서 가장 먼저 끝나는 것을 기준으로 골랐습니다.

4.2. 박인서

  • Greedy이다.
  • 위의 원준이 아이디어와 동일하다.

4.3. 곽정흠

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:07
Processing time 0.0185 sec