Assigning Meeting Room (Thuật toán tham lam)
package Advance;
import java.io.FileInputStream;
import java.util.Scanner;
public class AssigningMeetingRoom {
int Result;
int StartTime[];
int EndTime[];
int N;
public static void main(String[] args) throws Exception {
new AssigningMeetingRoom().inIt();
}
private void inIt() throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
N = sc.nextInt();
StartTime = new int[N+1];
EndTime = new int[N+1];
int addr = 0;
for (int i = 0; i < N; i++) {
addr = sc.nextInt();
StartTime[addr] = sc.nextInt();
EndTime[addr] = sc.nextInt();
}
sapxep();
Result = 1;
int temp = EndTime[1];
for (int i = 2; i <= N; i++) {
if(StartTime[i] >= temp){
temp = EndTime[i];
Result++;
}
}
System.out.println("#" + test_case + " " + Result);
}
}
private void sapxep() {
int temp = 0;
for (int i = 1; i <= N; i++) {
temp = EndTime[i];
for (int j = i + 1; j <= N; j++) {
if(EndTime[j] < temp){
temp = EndTime[j];
swap(i, j);
}
}
}
}
private void swap(int i, int j) {
int temp = EndTime[i];
EndTime[i] = EndTime[j];
EndTime[j] = temp;
temp = StartTime[i];
StartTime[i] = StartTime[j];
StartTime[j] = temp;
}
}
import java.io.FileInputStream;
import java.util.Scanner;
public class AssigningMeetingRoom {
int Result;
int StartTime[];
int EndTime[];
int N;
public static void main(String[] args) throws Exception {
new AssigningMeetingRoom().inIt();
}
private void inIt() throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
N = sc.nextInt();
StartTime = new int[N+1];
EndTime = new int[N+1];
int addr = 0;
for (int i = 0; i < N; i++) {
addr = sc.nextInt();
StartTime[addr] = sc.nextInt();
EndTime[addr] = sc.nextInt();
}
sapxep();
Result = 1;
int temp = EndTime[1];
for (int i = 2; i <= N; i++) {
if(StartTime[i] >= temp){
temp = EndTime[i];
Result++;
}
}
System.out.println("#" + test_case + " " + Result);
}
}
private void sapxep() {
int temp = 0;
for (int i = 1; i <= N; i++) {
temp = EndTime[i];
for (int j = i + 1; j <= N; j++) {
if(EndTime[j] < temp){
temp = EndTime[j];
swap(i, j);
}
}
}
}
private void swap(int i, int j) {
int temp = EndTime[i];
EndTime[i] = EndTime[j];
EndTime[j] = temp;
temp = StartTime[i];
StartTime[i] = StartTime[j];
StartTime[j] = temp;
}
}
Nhận xét
Đăng nhận xét