풀기 전:
회의실을 가장 많이 사용하는 수는 무엇일까? 마음속으로 상상해보자. 가장 처음에 오는 회의의 시간을 상상해보자.
그 회의의 종료시간은 종료시간이 가장적은 회의의 같거나 뒤에 있을 것이다. 같으면 상관없지만 뒤에 있다면
종료시간이 가장 적은 회의를 추가할 수 있는 경우 혹은 겹치는 경우인데 전자는 걍 추가하면 되는 거고
후자는 내가 설정한 가장 처음에 오는 회의의 종료시간이 종료시간이 가장 적은 회의의 시간으로 충분히 대체 가능하다.
그렇게 해서 종료시간이 가장 작은것을 먼저 정렬해 주어야 한다.
또한 이 문제는 회의시간이 끝나는 시간과 시작하는 시간이 같은 경우가 존재하는데 이 경우를 위해서 종료시간이 같은 경우 시작시간이 적은 시간이 우선적으로 앞에 나와야 한다.
예를 들어 4시 시작 5시 끝 이런 경우가 있고 5시 시작 5시 끝 이런 경우가 있다고 하면
5시 시작 5시 끝을 먼저 할 경우 4시 시작 5시 끝 이경우가 카운트가 안되지만
4시 시작 5시 끝 이 경우는 5시 시작 5시 끝을 카운트 해주기 때문이다.
자바(JAVA)
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.Collections;
class Pair implements Comparable{
int endTime;
int startTime;
Pair(int endTime,int startTime){
this.endTime=endTime;
this.startTime=startTime;
}
@Override
public int compareTo(Object o) {
if(o instanceof Pair){
Pair tmp=(Pair)o;
if(endTime<tmp.endTime){
return -1;
}
else if(endTime==tmp.endTime){
if(startTime<tmp.startTime){
return -1;
}
else if(startTime==tmp.startTime){
return 0;
}
else {
return 1;
}
}
else{
return 1;
}
}
return -1;
}
}
public class Main{
public static void main(String[] args) throws IOException {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
Vector<Pair> order=new Vector<>();
for(int i=0;i<n;i++){
int startTime= scanner.nextInt();
int endTime= scanner.nextInt();
order.add(new Pair(endTime,startTime));
}
Collections.sort(order);
int earliest=0;
int selected=0;
for(int i=0;i<order.size();i++){
int meetingBegin=order.get(i).startTime;
int meetingEnd=order.get(i).endTime;
if(earliest<=meetingBegin){
earliest=meetingEnd;
++selected;
}
}
System.out.println(selected);
}
}C++
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
bool Compare(pair<int, int> p1, pair<int, int> p2) {
if (p1.first == p2.first) {
return p1.second < p2.second;
}
else {
return p1.first < p2.first;
}
}
int main(void) {
int n;
cin >> n;
vector<pair<int, int>> order;
for (int i = 0; i < n; i++) {
int startTime; cin >> startTime;
int endTime; cin >> endTime;
order.push_back(make_pair(endTime,startTime));
}
sort(order.begin(), order.end(), Compare);
int earliest = 0;
int selected = 0;
for (int i = 0; i < order.size(); i++) {
int meetingBegin = order[i].second;
int meetingEnd = order[i].first;
if (earliest <= meetingBegin) {
earliest = meetingEnd;
++selected;
}
}
cout << selected;
}6개월 후에 다시 풀었을때:
한번에 풀이 방법이 떠올랐고 그 방법을 그림을 그려서 검증해보았다.
가장 많이 들어가려면 종료시간이 가장 짧은 것 순으로 정렬해야 했다.
그런데 이래도 틀린 경우가 있어서 확인해봤는데 회의종료시간이 같은 경우에다가 ,4-4 같은 경우도 존재했기에 종료시간이 같은 경우 시작 시간으로도 정렬했어야 했다.
예를 들면
8-8,7-8,6-8 이라면 최대 2개를 가질 수 있다 . 왜냐하면 6-8을 가지고 8-8도 사용하면 2번 회의실을 사용할 수 있기 때문이다. 하지만 8-8을 먼저 사용하면 1번 밖에 회의실을 못사용하기에 이 점을 유의한다.
import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
Pair pair[]=new Pair[n];
for(int i=0;i<n;i++){
pair[i]=new Pair();
pair[i].first= scanner.nextInt();
pair[i].second=scanner.nextInt();
}
Arrays.sort(pair);
int count=0;
int backValue=0;
for(int i=0;i<n;i++){
if(i==0||backValue<=pair[i].first){
count++;
backValue=pair[i].second;
}
else{
continue;
}
}
System.out.println(count);
}
public static class Pair implements Comparable{
int first;
int second;
@Override
public int compareTo(Object o) {
if(o instanceof Pair){
Pair p=(Pair) o;
if(this.second>p.second){
return 1;
}
else if(this.second==p.second){
if(this.first>p.first){
return 1;
}
else if(this.first<p.first){
return -1;
}
return 0;
}
else{
return -1;
}
}
return -1;
}
}
}