• Jan
  • Feb
  • Mar
  • Apr
  • May
  • Jun
  • Jul
  • Aug
  • Sep
  • Oct
  • Nov
  • Dec
  • Sun
  • Mon
  • Tue
  • Wed
  • Thu
  • Fri
  • Sat
  • 27
  • 28
  • 29
  • 30
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

#1931 회의실 배정

image

image

문제 정리

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수!

생각해보기

pair든 struct든,, 각 회의의 시작시간과 끝나는 시간을 같이 짝지어서 저장하는게 좋을 것 같다.
근데 뭘 기준으로 회의를 뽑아야 하지?

우선 생각나는 것들

  • 시작시간이 가장 빠른 순서대로

    • 0~6, 6~10, 응 안돼..~

  • 회의시간이 가장 짧은 순서대로

    • 3~5, 5~7, 12~14, 1~4,,? 응 안돼..~

  • 끝나는 시간이 가장 빠른 순서대로

    • 1~4, 5~7, 8~11, 12~14 …ㅇ ㅣ게 맞나….

    • 이거 같긴 한데 이게 최고의 방법인지 모르겠.. 이렇게 해도 되나…?

    • 이때 뇌리를 스치는 것… 바로

      image

      ㅇㅋ.. 바로 간다

코드 쓰기

끝나는 시간이 가장 빠른 순서대로 정렬 후 맨 처음 것 부터 뽑고,
맨처음.끝나는시간 이후에 시작하는 애들 중 끝나는 시간이 가장 빠른 애를 뽑는 식으로!

만약 끝나는 시간이 같은 애들이면 …? 흠 상관없겠군 꼭 오래 진행하는 회의를 뽑아야 되는 건 아니니까~!

끝나는 시간 순으로 정렬 마친 상태에서는
그 전에 끝난 회의 다음에 제일 빨리 시작하는 애 고르면 해가 나온다! 이미 끝나는 시간은 정렬이 돼 있으니까!

내 풀이

// BOJ-1931 회의실 배정
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef struct Meeting {
    int start;
    int end;
}Meeting;

// compare 함수
struct cmp {
    bool operator()(Meeting &a, Meeting &b) {
        if(a.end == b.end){
            return a.start > b.start;
        }
        else return a.end > b.end;
    }
};


int main() {
    int count, answer = 0;
    cin >> count;
    vector<Meeting> v;

    for(int i=0; i<count; i++){
        Meeting m;
        cin >> m.start >> m.end;
        
        v.push_back(m);
    }

    // 끝나는 시간이 가장 빠른 순서대로 정렬
    priority_queue<Meeting, vector<Meeting>, cmp> pq;
    for (int i=0; i<v.size(); i++) {
        pq.push(v[i]);
    }

    // 제일 일찍 끝나는 회의 뽑기
    int tempEnd = 0;

    // 그 후로 제일 일찍 끝나는 회의 뽑기
    while(!pq.empty()){
        // 다음 회의 시작시간이 tempEnd보다 작으면 pop
        if(pq.top().start < tempEnd) {
            pq.pop();
        } else {
            tempEnd = pq.top().end;
            pq.pop();
            answer++;
        }
    }

    cout << answer;
}

풀고 나서 알게된 것

typedef struct Meeting {
    int start;
    int end;
}Meeting;

이거 typedef 쓰는거 까먹지 말기!

오답노트

// BOJ-1931 회의실 배정
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef struct Meeting {
    int start;
    int end;
}Meeting;

// compare 함수
struct cmp {
    bool operator()(Meeting &a, Meeting &b) {
        return a.end >= b.end;
    }
};


int main() {
    int count, answer = 0;
    cin >> count;
    vector<Meeting> v;

    for(int i=0; i<count; i++){
        Meeting m;
        cin >> m.start >> m.end;
        
        v.push_back(m);
    }

    // 끝나는 시간이 가장 빠른 순서대로 정렬
    priority_queue<Meeting, vector<Meeting>, cmp> pq;
    for (int i=0; i<v.size(); i++) {
        pq.push(v[i]);
    }

    // 제일 일찍 끝나는 회의 뽑기
    int tempEnd = 0;

    // 그 후로 제일 일찍 끝나는 회의 뽑기
    while(!pq.empty()){
        // 다음 회의 시작시간이 tempEnd보다 작으면 pop
        if(pq.top().start < tempEnd) {
            pq.pop();
        } else {
            tempEnd = pq.top().end;
            answer++;
        }
    }

    cout << answer;
}

요렇게 했는데 시간 초과가 떴다. 왜일까….어딘가에서 무한루프가 걸렸을 수도 있겠는데…
priority queue를 잘 몰라서 그런가 ㅠ___ㅠ?

*if*(pq.top().start <= tempEnd)로 <를 <=로 바꿔줬더니 틀렸습니다가 떴다…
아 이건 틀린거 맞지.. =는 배제조건이 아니니까 ㄱ-

아 밑에 else문에서 pq.pop()을 안 해줬다. 뭐임 ;
근데 그래도 88퍼에서 틀렸습니다가 뜬다….. 도대체 뭘 놓친건데 ~!!
회의의 시작시간과 끝나는 시간이 같을 수도 있다 요놈 때문일까?
이것도 같이 고려된 것 같은데… ㄱ-

헐헐헐헐… 비교 함수에서 종료시간이 같을 때를 고려 안 해줘서 그렇다. 아까 위에서

만약 끝나는 시간이 같은 애들이면 …? 흠 상관없겠군 꼭 오래 진행하는 회의를 뽑아야 되는 건 아니니까~!

라고 했지만… 빡댁알이였던 것이다…
왜냐면 회의의 시작시간과 끝나는 시간이 같은 애가 있을 수도 있어서!!! ㄷ ㄷ ㄷ

1 4
8 8
6 8

이렇게 정렬되었을 때와

1 4
6 8
8 8

이렇게 정렬되었을 때는 카운팅되는 수가 다르다.

1번의 경우 1~4, 8~8이 카운팅되고 6~8은 pop되지만,
2번의 경우 1~4, 6~8, 8~8이 카운팅되기 때문!!

아 머리아파