[Ch.09 - Greedy] 02. 회의실 배정

2. 회의실 배정

 

설명

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.

각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

입력

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데

이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.

회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

예시 입력 1 

5
1 4
2 3
3 5
4 6
5 7

예시 출력 1

3

 

예시 입력 2 

3
3 3
1 3
2 3

예시 출력 2

2

---

---

import java.util.*;
  
class Meeting implements Comparable<Meeting>{
  int start, end;
  Meeting(int start, int end){
    this.start=start;
    this.end=end;
  }
  @Override
  public int compareTo(Meeting o){
    if(o.end==this.end)
      return this.start-o.start;
    else return this.end-o.end;
  }
}
public class Main {
  static Queue<Meeting> q = new PriorityQueue<>();
  public static void main(String[] args){
    //최대수의 회의 -> 큐에 넣고, 정렬 후 꺼내기
    Scanner kb=new Scanner(System.in);
    int n = kb.nextInt();
    for(int i=0;i<n;i++){
      int start = kb.nextInt();
      int end = kb.nextInt();
      q.offer(new Meeting(start, end));
    }
    System.out.println(solution(n));
  }
  static int solution(int n){
    //회의 시작시간<= 끝나는 시간이면 이용 가능
    int answer=1;
    Meeting m=q.poll();
    int tmp=m.end;
    while(!q.isEmpty()){
      m = q.poll();
      if(tmp<=m.start){
        answer++;
        tmp=m.end;
      }
    }
    return answer;
  }
}

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class Room implements Comparable<Room> {
	int st;
	int et;

	public Room(int st, int et) {
		this.st = st;
		this.et = et;
	}

	@Override
	public int compareTo(Room o) {
		if (this.et == o.et) {
			return this.st - o.st;
		} else
			return this.et - o.et;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		List<Room> list = new ArrayList<>();
		int n = kb.nextInt();
		for (int i = 0; i < n; i++) {
			int st = kb.nextInt();
			int et = kb.nextInt();
			Room r = new Room(st, et);
			list.add(r);
		}
		System.out.println(solution(list));

		// 조건 : et <= st이고, st가 더 크다.
	}

	public static int solution(List<Room> list) {
		Collections.sort(list);
		int answer = 0;
		int et = 0;
		for (Room r : list) {
			if (et <= r.st) {
				answer++;
				et=r.et;
			}
		}
		return answer;
	}
}

 

+) 세련된 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Meet implements Comparable<Meet> {
	int s, e;

	Meet(int s, int e) {
		this.s = s;
		this.e = e;
	}

	// 끝나는 시간 기준 오름차순 정렬
//	@Override
//	public int compareTo(Meet o){
//		return this.e-o.e;
//	}
	// 끝나는 시간 기준 오름차순 정렬 후, 끝나는 시간이 같으면, 시작 시간 기준 오름차순 정렬
	@Override
	public int compareTo(Meet o) {
		if (this.e == o.e)
			return this.s - o.s;
		//순서 : this -> 매개변수 순서, 앞에가 작고 뒤에가 커야 음수가 되므로 오름차순
		
		//끝나는 시간이 같으면, 시작 시간 기준 오름차순 정렬
		
		else
			return this.e - o.e;
		//끝나는 시간이 같지않으면, 끝나는 시간 기준 오름차순 정렬

	}

}

public class Main {
	public int solution(ArrayList<Meet> arr, int n) {
		int cnt=0;
		Collections.sort(arr);
		//arr 기준 정렬
		int end=0;
		for(Meet ob : arr) {
			if(end<=ob.s) {
				cnt++;
				end=ob.e;
			}						
		}
		
		return cnt;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Meet> arr = new ArrayList<Meet>();
		for (int i = 0; i < n; i++) {
			int s = kb.nextInt();
			int e = kb.nextInt();
			arr.add(new Meet(s, e));
		}
		System.out.println(T.solution(arr, n));
	}
}

---

#풀이 방법

1. PriortyQueue를 이용해, 끝나는 시간 기준 오름차순으로 큐를 정렬해서 풀이

2. 리스트에 Room객체를 넣고, 정렬시켜서, 해당 리스트를 돌면서 풀이

 

 

#리스트를 돌면서 푸는 풀이

1. 끝나는 시각이 제일 먼저 인 순으로 정렬하는데, 같을 경우 시작시간 오름차순

2. 끝나는 시각을 tmp변수로 넣어서, 다음 시작 시간과 비교해 answer++

import java.util.*;
class Work implements Comparable<Work>{
  public int start, end;
  Work(int start, int end){
    this.start=start;
    this.end=end;
  }
  @Override
  public int compareTo(Work o){
    if(this.end==o.end){
      return this.start-o.start;
    }
    return this.end-o.end;
  }
}
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    ArrayList<Work> list = new ArrayList<>();
    for(int i=0;i<n;i++){
      list.add(new Work(in.nextInt(), in.nextInt()));
    }
    System.out.println(solution(list));
  }
  static int solution(ArrayList<Work> list){
    int answer=0;
    Collections.sort(list);
    
    int tmp=0;
    for(Work w : list){
      //System.out.println(w.start+" "+w.end);
      if(tmp<=w.start){
        answer++;
        tmp=w.end;
      }
    }
    
    return answer;
  }
}

 

 

+) 02.22

import java.util.Scanner;
import java.util.*;
class Room{
    public int s;
    public int e;
    Room(int s, int e){
        this.s=s;
        this.e=e;
    }

}
public class Main {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n = in.nextInt();
        Room[] arr = new Room[n];

        for(int i=0;i<n;i++){
            arr[i]=new Room(in.nextInt(), in.nextInt());
        }
        Main main = new Main();
        System.out.println(main.solution(arr));
    }

    public int solution(Room[] arr){
        int answer=0;
        Arrays.sort(arr, (o1,o2)-> (o1.e==o2.e?o1.s-o2.s:o1.e-o2.e));

        int tmp=0;
        for(Room r: arr){
            if(tmp<=r.s) {
              answer++;
              tmp=r.e;
            }
        }

        return answer;
    }
}