Search⌘ K
Home
Courses
Decode the Coding Interview in Go: Real-World Examples

Feature #2: Show Busy Schedule

Explore how to implement a feature that shows a user's busy schedule by merging overlapping or consecutive meetings. This lesson teaches you to sort meetings by start time and merge intervals efficiently, ensuring privacy by hiding individual meeting details. You'll understand the algorithm's time and space complexity as you apply these concepts to calendar scheduling problems.

We'll cover the following...

Description

For the next feature, we want to find the times during which a user is busy. This feature is intended to show the busy hours of a user to other users without revealing the individual meeting slots. Therefore, if any meetings overlap or are back to back, then we want to merge their timings.

We will be provided a list of scheduled meetings, such as [[1, 4], [2, 5], [6, 8], [7, 9], [10, 13]]. In this schedule, [1, 4] and [2, 5], as well as [6, 8] and [7, 9], are overlapping. After merging these meetings, the schedule becomes [[1, 5], [6, 9], [10, 13]].

The illustration below shows a visual representation of the example.

Note: For simplicity, we are mapping the military timing to integers in the input. So, for example, 8:00 will be denoted by 8 in the code.

Solution

To solve this problem, it is best to sort the meetings based on the startTime. Then, we can determine if two meetings should be merged or not by processing them simultaneously.

Here is how we’ll implement this feature:

  • First, we will sort the meetings according to startTime.
  • Considering two meetings at a time, we will then check if the startTime of the second meeting is less than the endTime of the first meeting.
  • If the condition is true, merge the meetings into a new meeting and delete the existing ones.
  • Repeat the above steps until all the meetings are processed.
Go (1.16.5)
package main
import (
  "fmt"
  "sort"
  "math"
)
func mergeMeetings(meetingTimes [][]int) [][]int{
    var merged [][]int
    sort.Slice(meetingTimes, func(i, j int) bool {
        return meetingTimes[i][0] < meetingTimes[j][0] 
    })    
    for _, meeting := range meetingTimes {
        size := len(merged)
        if size == 0 || merged[size - 1][1] < meeting[0] {
            merged = append(merged, meeting)
        } else{
            merged[size - 1][1] = int(math.Max(float64(merged[size - 1][1]), float64(meeting[1])))
        }
    }
    return merged
}
func main() {
    meetingTimes1 := [][]int{{1, 4}, {2, 5}, {6, 8}, {7, 9}, {10, 13}}
    // First set of meetings
    print(mergeMeetings(meetingTimes1))
    // Second set of meetings
    meetingTimes2 := [][]int{{4, 7}, {1, 3}, {8, 10}, {2, 3}, {6, 8}}
    print(mergeMeetings(meetingTimes2))
}
Merge Overlapping Meetings

Complexity measures

Time complexity Space complexity
O
...