Skip to content

Instantly share code, notes, and snippets.

@abbeyjackson
Last active July 1, 2018 04:38
Show Gist options
  • Save abbeyjackson/ce5fe9c29b572be7d64cd4b5fcfbd66a to your computer and use it in GitHub Desktop.
Save abbeyjackson/ce5fe9c29b572be7d64cd4b5fcfbd66a to your computer and use it in GitHub Desktop.
//: 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment