greedy.kt

class Course(val name: String, val start: Short, val end: Short)

/** For list of courses, print best schedule for a single classroom.
 *
 * The best schedule for a classroom is the one that has the most classes
 * scheduled for it, with no classes overlapping with another class.
 */

fun bestSchedule(classes: MutableList<Course>): List<String> {
    val schedule = mutableListOf<String>()

    // Strategy: greedy algorithm ---
    // - find the earliest ending course and add to schedule
    // - remove all courses that could no longer be scheduled
    // - repeat until no courses are left
    //
    // This always provides the optimal solution.
    //
    // The runtime for this implementation is O(n^2); this could be improved to
    // O(n log n) by keeping the courses as a presorted-by-start-time
    // LinkedList, and having a separate LinkedList sorted by end time. By
    // keeping track of our progress in both LLs, we could ensure we never see
    // an inapplicable item, thereby doing the main work in O(n) (plus the O(n
    // log n) from the sorting).
    
    while (classes.isNotEmpty()) {
        // the "!!" on the next line is to indicate that, although the method
        // given *can* sometimes return null (if no min item found), we know it
        // would never return null. The !! reassure the type-checking system,
        // thereby allowing us to treat it as always safely non-null.
        classes.minByOrNull { it.end }!!.let { earliestEnding ->
            schedule.add(earliestEnding.name)
            classes.removeIf { it.start < earliestEnding.end }
        }
    }

    return schedule
}

val classes = mutableListOf(
    Course("art", 900, 1000),
    Course("eng", 930, 1030),
    Course("math", 1000, 1100),
    Course("cs", 1030, 1130),
    Course("music", 1100, 1200),
)

check(bestSchedule(classes) == listOf("art", "math", "music"))