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;
}
}

Nhận xét

Bài đăng phổ biến từ blog này

Nâng cấp máy tính (Thuật toán quay lui)

Tấn công thành trì (Thuật toán Prim tìm cây khung lớn nhất)

Battle City (Thuật toán BFS)