Saturday, March 11, 2023

Coding Challenge #19 Min # of classrooms based on class start/stop times

 // Daily Coding Challenge #21
/*
Given an array of start and stop times for classes, determine by observing where the times overlap how many classrooms would be needed?
Example: [ [1,3], [2,3], [4,5] ] => 2 classrooms needed (indices 1 & 2 are both active during hour 2: 1,2,3 & 2,3)
*/
function calc(ary){
    // we're going to go around and check for each start/stop time whether another start/stop time in the array overlaps with it, counting how many and storing the max.
    var maxOverlaps = 0;
    for(var xint = 0, len = ary.length;xint < len;xint++){
        var overlaps = 0;
        for(var yint = 0, len2 = ary.length;yint < len2;yint++){
            if(xint == yint) continue; // don't compare to itself
            // detecting collision is kinda hard, eh? but detecting lack of collision is easy: if start & stop of A are less than B's start, or A's start & stop are greater than B's stop, it occupies a different range on the one-dimensional plane.
            // for our example, saying A starts at 1 and ends at 2, and B starts at 2 and ends at 3, we will declare this not to overlap, as the bulk of their sessions will not overlap even if the physical students cannot swap places in under a second
            if(!( (ary[xint][0] <= ary[yint][0] && ary[xint][1] <= ary[yint][0])
            || (ary[xint][0] >= ary[yint][1] && ary[xint][0] >= ary[yint][1]) )){
                // failed to not overlap
                // aka overlap
                overlaps++;
                console.log(ary[xint].toString() + " and " + ary[yint].toString() + " overlapped.");
            }
        }
        if(overlaps > maxOverlaps) maxOverlaps = overlaps;
    }
    maxOverlaps += 1; // 1 classroom + 1 classroom for each overlap
    console.log('Number of classrooms needed: ' + maxOverlaps);
}

No comments:

Post a Comment

Coding Challenge #54 C++ int to std::string (no stringstream or to_string())

Gets a string from an integer (ejemplo gratis: 123 -> "123") Wanted to come up with my own function for this like 10 years ago ...