Algorithm 문제풀이/greedy

[BOJ] 백준 1931 - 회의실배정 (JAVA)

cjsong 2019. 6. 18. 22:31

처음에 푼 코드. 재귀돌면서 따져주니깐 6% 에서 시간초과

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package greedy;
 
 
public class Main1931_회의실배정 {
    static int maxNum = Integer.MIN_VALUE;
    private static Pair[] conference;
    private static boolean[] visited;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        conference = new Pair[N];
        visited = new boolean[N];
        for (int i = 0; i < conference.length; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            conference[i] = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));// 회의시간 저장
        }
 
        int endTime = 0;
        for (int i = 0; i < conference.length; i++) {
            if (endTime < conference[i].end) {
                endTime = conference[i].end;
            }
        }
        dfs(0, endTime, 1);
        System.out.println(maxNum);
 
    }// end of main
 
    public static void dfs(int index, int endTime, int count) {
        if (conference[index].end == endTime) {
            maxNum = maxNum < count ? count : maxNum;
            return;
        }
 
        for (int i = 0; i < conference.length; i++) {
            if (conference[index].end <= conference[i].start) {
                if (!visited[index]) {
                    visited[index] = true;
                    dfs(i, endTime, count + 1);
                    visited[index] = false;
                }
            }
        }
    }
 
    static class Pair implements Comparable<Pair>{
        int start;
        int end;
 
        public Pair(int start, int end) {
            super();
            this.start = start;
            this.end = end;
        }
 
        @Override
        public int compareTo(Pair o) {
            // TODO Auto-generated method stub
            return 0;
        }
 
    }
}// end of class
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none; color:white">cs
 

==============================================================================

시작하는 시간으로 기준을 잡아버리면 반례가 발생해서 끝나는 시간으로 오름차순으로 정렬해주고 끝나는 시간이 같을 때 시작하는 시간 기준으로 정렬

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package greedy;
 
 
public class Main1931_회의실배정 {
    static int maxNum = Integer.MIN_VALUE;
    private static Pair[] conference;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        ArrayList<Pair >conference = new ArrayList<Pair>();
        
        for(int i=0; i < N; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            conference.add(new Pair(start, end));
        }
        
        int result = 0;
        int prevEnd = 0;
        for(Pair t:conference) {
            if(prevEnd <= t.getStart()) {
                    result += 1;
                    prevEnd = t.getEnd();
            }
        }
        System.out.println(result);
 
    
        
 
    }// end of main
 
 
 
    static class Pair implements Comparable<Pair> {
        private int start;
        private int end;
 
        public Pair(int start, int end) {
            super();
            this.start = start;
            this.end = end;
        }
 
        public int getStart() {
            return start;
        }
 
        public void setStart(int start) {
            this.start = start;
        }
 
        public int getEnd() {
            return end;
        }
 
        public void setEnd(int end) {
            this.end = end;
        }
 
        @Override
        public int compareTo(Pair o) {
            if (this.end < o.getEnd()) {
                return -1;
            } else if (this.end == o.getEnd()) {
                if (this.start < o.getStart()) {
                    return -1;
                } else if (this.start == o.getStart()) {
                    return 0;
                } else {
                    return 1;
                }
            } else {
                return 1;
            }
        }
 
    }
}// end of class
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none; color:white">cs