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.