Algoritm Laboratoarele 5-7
19 Noiembrie, 2013 - 22:30
Intrucat unii dintre studenti nu au inteles algoritmul pentru determinarea numarului de locuri libere intr-un anumit interval, in functie de orar si de rezervarile existente, il atasez aici, intr-o forma de pseudocod foarte asemanatoare cu Java:
getAvailableSeats(interval) {
result = numberOfSeats;
// check if interval is in timetable
for-each(currentInterval in timetable)
if (interval.getStartingTime() < currentInterval.getStartingTime() || interval.getEndingTime() > currentInterval.getEndingTime())
return -1;
// determine intersection points with existing reservations
GregorianCalendar[] intersectionPoints;
for-each(currentReservation in reservations) {
Interval intersection = getIntervalIntersection(interval,currentReservation.getInterval());
if (intersection != null) {
if (!intersectionPoints.contains(intersection.getStartingTime())
intersectionPoints.add(intersection.getStartingTime());
if (!intersectionPoints.contains(intersection.getEndingTime())
intersectionPoints.add(intersection.getEndingTime());
}
}
if (!intervalIntersections.isEmpty()) {
// sort intersection points
sort(intersectionPoints);
// get number of seats available for each subinterval
for (i=0; i<intersectionPoints.size()-1; i++) {
// create subinterval
currentInterval = new Interval(intersectionPoints[i],intersectionPoints[i+1]);
currentNumberOfSeats = numberOfSeats;
// determine number of seats available in the subinterval by intersection with
// occupied seats in reservations
for (j=0; j<reservations.size(); j++)
if (getIntervalIntersection(currentInterval,reservations[j].getInterval())!=null)
currentNumberOfSeats -= reservations[j].getNumberOfSeats();
// number of seats available in the interval is given by the minimum number
// of seats available in all subintervals
if (result > currentNumberOfSeats)
result = currentNumberOfSeats;
}
}
return result;
}
Studentii care au implementat incorect acest algoritm vor fi penalizati cu 1p din cele 4 p disponibile exercitiului 4 doar in laboratorul 5, primind punctaj maxim pentru laboratoarele 6 si 7.