merged meetings

//: Playground - noun: a place where people can play

import UIKit
import Foundation

// Merge overlapping times
// https://www.interviewcake.com/question/swift/merging-ranges?course=fc1&section=array-and-string-manipulation

/** Your company built an in-house calendar tool called HiCal. You want to add a feature to see the times in a day when everyone is available.
 */

/// PROVIDED:
class Meeting: CustomStringConvertible {
    
    var startTime: Int
    var endTime: Int
    
    init(startTime: Int, endTime: Int) {
        
        // number of 30 min blocks past 9:00 am
        self.startTime = startTime
        self.endTime = endTime
    }
    
    var description: String {
        return "(\(startTime), \(endTime))"
    }
}

// Example Data
let exampleInput = [
    Meeting(startTime: 0, endTime: 1), Meeting(startTime: 3, endTime: 5),
    Meeting(startTime: 4, endTime: 8), Meeting(startTime: 9, endTime: 12),
    Meeting(startTime: 9, endTime: 10)
]
let exampleReturn = [
    Meeting(startTime: 0, endTime: 1),
    Meeting(startTime: 3, endTime: 8),
    Meeting(startTime: 9, endTime: 12)
]

/** Write a function mergeRanges() that takes an array of multiple meeting time ranges and returns an array of condensed ranges.
 
 Do not assume the meetings are in order. The meeting times are coming from multiple teams.
 
 Write a solution that's efficient even when we can't put a nice upper bound on the numbers representing our time ranges. Here we've simplified our times down to the number of 30-minute slots past 9:00 am. But we want the function to work even for very large numbers, like Unix timestamps. In any case, the spirit of the challenge is to merge meetings where startTime and endTime don't have an upper bound.
 */

// Me

// OPTIMIZING

func optimized(from meetings: [Meeting]) -> [Meeting] {
    print("start optimized")
    let startTime = CFAbsoluteTimeGetCurrent()
    
    let unmergedMeetings = meetings.map { Meeting(startTime: $0.startTime, endTime: $0.endTime) }
        .sorted { $0.startTime <= $1.startTime }
    var mergedMeetings = [Meeting]()
    
    for meeting in unmergedMeetings {
        if let lastMeeting = mergedMeetings.last,
            meeting.startTime <= lastMeeting.endTime {
            lastMeeting.endTime = meeting.endTime >= lastMeeting.endTime ? meeting.endTime : lastMeeting.endTime
        } else {
            mergedMeetings.append(meeting)
        }
    }
    
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print("Time elapsed for optimized: \(timeElapsed) s.")
    
    print("optimized result: \(mergedMeetings)")

    return mergedMeetings
}

// TESTING OPTIMIZED
 optimized(from: exampleInput)

/**
 Time elapsed for optimized: 0.00802004337310791 s.
 optimized result: [(0, 1), (3, 8), (9, 12)]
 Time elapsed for official: 0.0121129751205444 s.
 official result: [(0, 1), (3, 8), (9, 12)]
 */
// Sorting an array takes Ologn time which is very fast, then going through the array one time is On
// so the total complexity for the optimized solution is Onlogn which is much faster than the first
// solution which is On^2

/// Official Solution
func mergeRangesOfficial(in meetings: [Meeting]) -> [Meeting] {
    print("start official")
    let startTime = CFAbsoluteTimeGetCurrent()
    
    // make a copy so we don't destroy the input
    var sortedMeetings = meetings.map { Meeting(startTime: $0.startTime, endTime: $0.endTime) }
    
    // sort by start time
    sortedMeetings.sort { $0.startTime < $1.startTime }
    
    // initialize mergedMeetings with the earliest meeting
    var mergedMeetings = [sortedMeetings[0]]
    
    for i in 1..<sortedMeetings.count {
        let currentMeeting = sortedMeetings[i]
        let lastMergedMeeting = mergedMeetings[mergedMeetings.count - 1]
        
        if currentMeeting.startTime <= lastMergedMeeting.endTime {
            
            // if the current meeting overlaps with the last merged meeting, use the
            // later end time of the two
            lastMergedMeeting.endTime = max(lastMergedMeeting.endTime, currentMeeting.endTime)
        } else {
            
            // add the current meeting since it doesn't overlap
            mergedMeetings.append(currentMeeting)
        }
    }
    
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print("Time elapsed for official: \(timeElapsed) s.")
    
    print("official result: \(mergedMeetings)")
    
    return mergedMeetings
}

mergeRangesOfficial(in: exampleInput)