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
import java.util.*;
class Job {
int start, end;
public Job(int start, int end) {
this.start = start;
this.end = end;
}
}
public class JobScheduling {
public static void main(String[] args) {
List<Job> jobs = new ArrayList<>();
jobs.add(new Job(7, 8));
jobs.add(new Job(3, 7));
jobs.add(new Job(1, 5));
jobs.add(new Job(5, 9));
jobs.add(new Job(0, 2));
jobs.add(new Job(6, 8));
jobs.add(new Job(1, 6));
List<List<Job>> machines = new ArrayList<>();
int n = jobs.size();
// 1. 시작 시간으로 정렬
Collections.sort(jobs, new Comparator<Job>() {
@Override
public int compare(Job o1, Job o2) {
return o1.start - o2.start;
}
});
// 2. 작업 배정
for (int i = 0; i < n; i++) {
Job job = jobs.get(i);
boolean assigned = false;
for (List<Job> machine : machines) {
if (machine.get(machine.size() - 1).end <= job.start) {
machine.add(job); // 현재 작업을 기계에 배정
assigned = true; // 작업이 배정됐음을 표시
break; // 다음 작업으로 이동
}
}
if (!assigned) {
List<Job> newMachine = new ArrayList<>();
newMachine.add(job); // 현재 작업을 새로운 기계에 배정
machines.add(newMachine); // 새 기계를 기계 리스트에 추가
}
}
// 3. 결과 출력
for (int i = 0; i < machines.size(); i++) {
System.out.print("Machine " + (i+1) + ": "); // 기계 번호 출력
List<Job> machine = machines.get(i);
for (int j = 0; j < machine.size(); j++) {
Job job = machine.get(j);
System.out.print("(" + job.start + ", " + job.end + ") "); // 작업 시간 출력
}
System.out.println();
}
}
}
실행결과:
작업 1: (0, 2) (3, 7) (7, 8)
작업 2: (1, 5) (5, 9)
작업 3: (1, 6) (6, 8)
이 문제는 “작업 스케줄링 (Job Scheduling)” 문제를 해결하는 알고리즘입니다. 이 문제는 여러 개의 작업이 있을 때, 각 작업의 시작 시간과 종료 시간이 주어지고, 이를 최소한의 기계 수를 사용하여 모든 작업을 처리하는 문제입니다. 이 알고리즘은 그리디 알고리즘을 사용하여 이 문제를 해결합니다.
이 알고리즘은 다음과 같은 과정으로 작동합니다:
1.작업 리스트를 시작 시간을 기준으로 정렬합니다.
-시작 시간이 빠른 작업부터 처리하면, 기계를 최소한으로 사용할 수 있기 때문입니다.
2.모든 작업을 하나씩 검사하여, 이 작업을 배정할 수 있는 가장 빠른 기계를 찾습니다.
-이전에 배정된 작업 중에서 종료 시간이 가장 빠른 작업이 끝난 후에 이 작업을 처리할 수 있는 기계를 선택합니다.
-만약 모든 기계에서 이 작업을 처리할 수 없다면, 새로운 기계를 만들어 이 작업을 처리합니다.
3.각 기계가 어떤 작업들을 처리하는지 출력합니다.
알고리즘 코드에서는 작업을 나타내는 Job 클래스와, 작업 리스트를 저장하는 jobs 리스트, 기계 리스트를 저장하는 machines 리스트를 사용합니다. 또한, 각 작업의 시작 시간으로 jobs 리스트를 정렬하고, 모든 작업을 하나씩 검사하여 이를 적절한 기계에 배정하고 결과를 출력합니다.
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
import java.util.*;
class Main {
static class Meeting implements Comparable<Meeting> {
int start, end;
public Meeting(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Meeting o) {
if (this.end == o.end) {
return this.start - o.start;
}
return this.end - o.end;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<Meeting> meetings = new ArrayList<>();
for (int i = 0; i < n; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
meetings.add(new Meeting(start, end));
}
Collections.sort(meetings);
int count = 1;
int end = meetings.get(0).end;
for (int i = 1; i < n; i++) {
if (end <= meetings.get(i).start) {
count++;
end = meetings.get(i).end;
}
}
System.out.println(count);
}
}
입력:
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
실행결과:
4
이 코드는 회의실 배정 문제를 해결하는 코드입니다. 주어진 n개의 회의들에 대해, 각 회의는 시작 시간과 끝나는 시간이 주어지며, 하나의 회의실에서 겹치지 않게 회의를 배정하는 것이 목표입니다. 이를 위해 회의 종료 시간이 빠른 순으로 회의를 정렬하고, 현재 회의실에서 마지막으로 배정된 회의의 종료 시간과 다음 회의의 시작 시간을 비교하여 회의를 배정하며, 가능한 회의의 개수를 구합니다.
이 코드의 시간 복잡도는 리스트를 정렬하는 과정에서 O(n log n)이 소요되며, 순회하는 과정에서 O(n)이 소요되므로, 전체적으로 O(n log n)의 시간 복잡도를 가집니다.
