Mamy następujący problem:
Problem wyboru zajęć: dany jest zbiór n zajęć, każe z nich ma czas rozpoczęcia i czas zakończenia.
Dysponujesz jedną salą wykładową, w której przez określoną ilość godzin w ciągu dnia mogą się
odbywać zajęcia. W danej chwili w sali mogą się odbywać tylko jedne zajęcia. Jeśli jedne zajęcia
kończą się w czasie t, to kolejne mogą się zaczynać w czasie t. Zaproponuj algorytm, który
wybierze zajęcia w taki sposób, aby ich łączny czas trwania był możliwie najdłuższy.Plik wejściowy:
Kolejne linie: czas rozpoczęcia i zakończenia poszczególnych zajęć
0 3
1 3
2 4
2 5
4 8
6 8
7 10
8 10
0 2
1 2Plik wyjściowy:
Pierwsza linia: łączna ilość godzin wybranych zajęć.
Kolejne linie: czas rozpoczęcia i zakończenia wybranych zajęć
Ostatnia linia: ilość operacji elementarnych, które się wykonały podczas działania programu
10
0 2
2 4
4 8
8 10
10
Mój algorytm:
/*
Problem wyboru zajęć: dany jest zbiór n zajęć, każe z nich ma czas rozpoczęcia i czas zakończenia.
Dysponujesz jedną salą wykładową, w której przez określoną ilość godzin w ciągu dnia mogą się
odbywać zajęcia. W danej chwili w sali mogą się odbywać tylko jedne zajęcia. Jeśli jedne zajęcia
kończą się w czasie t, to kolejne mogą się zaczynać w czasie t. Zaproponuj algorytm, który
wybierze zajęcia w taki sposób, aby ich łączny czas trwania był możliwie najdłuższy.
Plik wejściowy:
Kolejne linie: czas rozpoczęcia i zakończenia poszczególnych zajęć
Plik wyjściowy:
Pierwsza linia: łączna ilość godzin wybranych zajęć.
Kolejne linie: czas rozpoczęcia i zakończenia wybranych zajęć
Ostatnia linia: ilość operacji elementarnych, które się wykonały podczas działania programu
Przykład:
Plik wejściowy:
0 3
1 3
2 4
2 5
4 8
6 8
7 10
8 10
0 2
1 2
Plik wyjściowy:
10
0 2
2 4
4 8
8 10
10
REF:
http://www.cs.put.poznan.pl/arybarczyk/ProgrDynamiczne.pdf
*/
package asd_4_2;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;
/**
* @author GrzegorzOginski at gmail dot com
*/
public class Asd_4_2 {
static class Hour implements Comparable<Hour> {
private static int count;
private final Integer startHour;
private final Integer endHour;
private final int obiectId;
Hour(final int s, final int e) {
startHour = s;
endHour = e;
count++;
obiectId = count;
}
@Override
public int compareTo(Hour h) {
return this.endHour.compareTo(h.endHour);
}
@Override
public String toString() {
return Integer.toString(this.startHour + this.endHour);
}
}
static class CompareByEnd implements Comparator<Hour> {
@Override
public int compare(Hour h1, Hour h2) {
return h1.endHour < h2.endHour ? -1 : Objects.equals(h1.endHour, h2.endHour) ? 0 : 1;
}
}
static class CompareByStart implements Comparator<Hour> {
@Override
public int compare(Hour h1, Hour h2) {
return h1.startHour < h2.startHour ? -1 : Objects.equals(h1.startHour, h2.startHour) ? 0 : 1;
}
}
//weź liste
//dodaj pierwsze zajecia do zbioru (najszybciej sie konczące)
//dla wszystkich zajec
//sprawdż czy czas zakoczenia nastepnego zajecia nie naklada sie na zajecia juz dodane
//jesli nie to dodaj do zbioru wyjsciowego
//jestli tak to pomin
//zwroc zbior
public static int elemOpsCount = 0; //licznik operacji elementarnych
static List<Hour> selectHour2(List<Hour>h){
List<Hour> selectedHours = new LinkedList<>(); //Lista zajec posortowana po end
selectedHours.add(h.get(0)); //Dodanie pierwszych zajęć jako najbardziej optymalnych (najwcześniej się kończą)
for(int i = 1, j=i-1; i < h.size(); ++i) //iterujemy po liscie od 1 do h.size()
{
elemOpsCount++; //zliczanie operacji elementarnych
if(h.get(j).endHour <= h.get(i).startHour) //if czas zakończenia aktualnych zajec <= zajeciąm prze które iterujemy
{
selectedHours.add(h.get(i)); //dodajemy te zajecia do listy
j = i; //aktualne zajecia wskazują teraz na iteratora
}
}
return selectedHours; //zwróc Liste zajec najlepiej wykorzystujacej zasób sali
}
//returens id of object
static Integer[] selectHour(List<Hour> h) {
Integer[] selectedHours = new Integer[h.size()];
selectedHours[0] = h.get(0).obiectId; //set first
for (int i = 1, j = i-1; i < h.size(); i++) {
if (h.get(j).endHour <= h.get(i).startHour) {
selectedHours[i] = h.get(i).obiectId;
j = i;
}
}
return selectedHours;
}
/**
* @param args the command line arguments
* @exception java.io.FileNotFoundException
*/
public static void main(String[] args) throws FileNotFoundException, IOException {
final String inputFile = "src/4_2_in";
final String outputFile = "src/4_2_out";
List<Hour> hours = new LinkedList<>();
Scanner scanner = new Scanner(new File(inputFile));
while (scanner.hasNext()) {
hours.add(new Hour(scanner.nextInt(), scanner.nextInt()));
}
//sort hours
Collections.sort(hours, new CompareByEnd()); //sort by end of hour range
//check if works, compute some
List<Hour> hours2 = selectHour2(hours);
int sum = 0;
for(Hour h: hours2){
sum += (h.endHour-h.startHour);
System.out.println(h.startHour+" "+h.endHour);
}
//save output file
File outFile = new File(outputFile);
try(PrintWriter printWriter = new PrintWriter(outFile)){
printWriter.println(sum);
for(Hour h: hours2){
printWriter.println(h.startHour+" "+h.endHour);
}
printWriter.println(elemOpsCount);
}
}
}
Napisałem algorytm który dla podanych wejściowych zwraca poprawne wyniki, ale prowadzący podał mi dane wejściowe które dają nie takie wyniki jak by oczekiwał. Otóz dla danych jak niżej mój algorytm zwraca wynik nieoptymalny (02 35 68 zamiast 03 35 68)
0 2
0 3
3 5
6 8
Jak naprawić ten algorytm by zawsze był wynik optymalny? Proszę o wskazówki.