회의실 시간표

회의실 시간표

n개의 회의들에 대하여 각 시작시간, 끝나는 시간이 주어져 있고
회의가 겹치지 않게 회의할 수 있는 최대 수를 찾아라

ex)
5
1 4
2 3
3 5
4 6
5 7

출력 : 3

ex)
3
3 3
1 3
2 3

출력 : 2

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

class Meeting implements Comparable<Meeting> {
    int start;
    int end;

    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Meeting meeting) {
        if (this.end == meeting.end) return this.start - meeting.start;
        else return this.end - meeting.end;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        ArrayList<Meeting> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            list.add(new Meeting(start, end));
        }

        list.sort(Meeting::compareTo);

        int cnt = 0;
        int endTime = 0;
        for (Meeting meeting : list) {
            if (meeting.start >= endTime) {
                cnt++;
                endTime = meeting.end;
            }
        }

        System.out.println(cnt);
    }
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Meeting implements Comparable<Meeting> {
    int index;
    int start;
    int end;

    public Meeting(int index, int start, int end) {
        this.index = index;
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Meeting meeting) {
        return this.start - meeting.start;
    }
}

public class Main {

    static Queue<Meeting> queue = new LinkedList<>();
    static ArrayList<Meeting> list = new ArrayList<>();
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        queue.offer(new Meeting(0, 0, 0));
        list.add(new Meeting(0, 0, 0));

        for (int i = 0; i < n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            list.add(new Meeting(i + 1, start, end));
        }
        list.sort(Meeting::compareTo);
        System.out.println(BFS());
    }

    static int BFS() {
        int cnt = -1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            cnt = cnt + 1;

            for (int i = 0; i < size; i++) {
                Meeting meeting = queue.poll();
                int index = meeting.index;
                for (int j = index; j < list.size(); j++) {
                    if (list.get(j).start >= meeting.end && list.get(j).start != meeting.start) {
                        queue.add(list.get(j));
                    }
                }
            }
        }

        return cnt;
    }
}

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

class Meeting implements Comparable<Meeting> {
    int start;
    int end;

    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Meeting meeting) {
        return this.start - meeting.start;
    }
}

public class Main {

    static ArrayList<Meeting> list = new ArrayList<>();
    static int n;
    static int totalCnt;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        list.add(new Meeting(0, 0));
        for (int i = 0; i < n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            list.add(new Meeting(start, end));
        }

        list.sort(Meeting::compareTo);

        DFS(0, 0, 0, 0, 0);

        System.out.println(totalCnt);
    }

    static void DFS(int index, int cnt, int lastEnd, int start, int end) {
        if (lastEnd > start) {
            if(cnt > totalCnt) totalCnt = cnt;
        } else {
            for (int i = index + 1; i <= n; i++) {
                DFS(i, cnt + 1, end, list.get(i).start, list.get(i).end);
            }
        }
    }
}