Home/

...

/

Introduction

Introduction

Real-world problems

The Google Calendar application is developed by Google as part of the GSuite. Google Calendar makes people’s everyday lives easier by helping them manage events and reminders. Companies especially benefit from it greatly because it can also be used to manage events across multiple calendars. This way, companies can track the availability of employees and rooms to schedule meetings efficiently.

Following are a few scenarios and problems that relate to developing and implementing meeting management features.

Show Busy Schedule

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]].

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

The illustration below shows a visual representation of the example.

Schedule a New Meeting

For this feature, we have a user who wants to add a new meeting to their tentative meeting schedule. First, we need to add the new meeting to the user’s schedule. Then, we want to make refinements in the schedule to merge some of the meetings. The user’s initial schedule will have no conflicts; however, the new meeting might overlap with one or more of the older ones. Therefore, we can save time by merging some of the meetings that can be held together in the same venue (this can be done for the tasks that can run simultaneously). The meetings can only be merged if the new meeting time overlaps or is adjacent to an existing meeting. We merge these meetings to eliminate conflict.

Suppose we are given a list of non-overlapping scheduled meetings, such as {{1, 3}, {4, 6}, {8, 10}, {10, 12}, {13, 15}, {16, 18}}. The new meeting, which we need to fit into this already busy schedule, is also given; it is {9, 13}. In this case, the new meeting overlaps with two meetings: {8, 10} and {10, 12}. After merging, the meeting is adjacent to the {13, 15} meeting, so {13, 15} will also be merged. Hence, the final schedule for the day will be: {{1, 3}, {4, 6}, {8, 15}, {16, 18}}.

The illustration below shows a visual representation of the example.

Find Common Meeting Times

We want to implement a feature that lets us see when two users are busy at the same time. We will be given the meeting schedule of two users, and we have to find all the overlapping meetings to determine when both of them are unavailable.

We will also assume that each user’s schedule is free of conflicting meetings, meaning their schedules are non-overlapping. Moreover, the meetings have been already sorted based on their starting time.

Let’s say that we are given the following pairs of meeting schedules: {{1, 3}, {5, 6}, {7, 9}} and {{2, 3}, {5, 7}}. In this example, we can see that both of the users will be busy at the following times: {{2, 3}, {5, 6}}.

Take a look at the illustration given below:

Dry-run templates

The following is the implementation of the solution provided for the Intervals Intersection (medium) problem:

Press + to interact
Python 3.5
def merge(intervals_a, intervals_b):
  result = []
  i, j, start, end = 0, 0, 0, 1
  while i < len(intervals_a) and j < len(intervals_b):
    # check if intervals overlap and intervals_a[i]'s start time lies within the other intervals_b[j]
    a_overlaps_b = intervals_a[i][start] >= intervals_b[j][start] and \
                   intervals_a[i][start] <= intervals_b[j][end]
    # check if intervals overlap and intervals_b[j]'s start time lies within the other intervals_a[i]
    b_overlaps_a = intervals_b[j][start] >= intervals_a[i][start] and \
                   intervals_b[j][start] <= intervals_a[i][end]
    # store the the intersection part
    if (a_overlaps_b or b_overlaps_a):
      result.append([max(intervals_a[i][start], intervals_b[j][start]), min(
        intervals_a[i][end], intervals_b[j][end])])
    # move next from the interval which is finishing first
    if intervals_a[i][end] < intervals_b[j][end]:
      i += 1
    else:
      j += 1
  return result
def main():
  print("Intervals Intersection: " + str(merge([[1, 3], [5, 6], [7, 9]], [[2, 3], [5, 7]])))
  print("Intervals Intersection: " + str(merge([[1, 3], [5, 7], [9, 12]], [[5, 10]])))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

intervals_a: [[1, 3], [5, 6], [7, 9]]
intervals_b: [[2, 3], [5, 7]]

Iteration No. 1

Line No.

i

j

intervals_a[i]

intervals_b[j]

a_overlaps_b

b_overlaps_a

result

-

3

0

0

-

-

-

-

[]

1

7-12

0

0

(1,3)

(2,3)

false

true

[]

1

15-17

0

0

(1,3)

(2,3)

false

true

[[2, 3]]

2

7-12

0

1

(1,3)

(5,7)

false

false

[[2, 3]]

2

15-17

0

1

(1,3)

(5,7)

false

false

[[2, 3]]

3

7-12

1

1

(5,6)

(5,7)

true

true

[[2, 3]]

3

15-17

1

1

(5,6)

(5,7)

true

true

[[2, 3], [5, 6]]

4

7-12

2

1

(7,9)

(5,7)

true

false

[[2, 3], [5, 6]]

4

15-17

2

1

(7,9)

(5,7)

true

false

[[2, 3], [5, 6], [7, 7]]

Sample Input #2

intervals_a: [[1, 3], [5, 7], [9, 12]]
intervals_b: [[5, 10]]

Iteration No. 1

Line No.

i

j

intervals_a[i]

intervals_b[j]

a_overlaps_b

b_overlaps_a

result

-

3

0

0

-

-

-

-

[]

1

7-12

0

0

(1,3)

(5,10)

false

false

[]

1

15-17

0

0

(1,3)

(5,10)

false

false

[]

2

7-12

1

0

(5,7)

(5,10)

true

true

[]

2

15-17

1

0

(5,7)

(5,10)

true

true

[[5, 7]]

3

7-12

2

0

(9,12)

(5,10)

true

false

[[5, 7]]

3

15-17

2

0

(9,12)

(5,10)

true

false

[[5, 7], [9, 10]]

Trace Generation

Press + to interact
Python 3.5
def merge(intervals_a, intervals_b):
  result = []
  i, j, start, end = 0, 0, 0, 1
  while i < len(intervals_a) and j < len(intervals_b):
    print("\n\ti: " + str(i))
    print("\tj: " + str(j))
    print("\tChecking overlap for intervals: ", end=" ")
    print("(" + str(intervals_a[i][start]) + "," + str(intervals_a[i][end]) + ")",end=" ")
    print("(" + str(intervals_b[j][start]) + "," + str(intervals_b[j][end]) + ")")
    
    # check if intervals overlap and intervals_a[i]'s start time lies within the other intervals_b[j]
    a_overlaps_b = intervals_a[i][start] >= intervals_b[j][start] and \
                   intervals_a[i][start] <= intervals_b[j][end]
    # check if intervals overlap and intervals_b[j]'s start time lies within the other intervals_a[i]
    b_overlaps_a = intervals_b[j][start] >= intervals_a[i][start] and \
                   intervals_b[j][start] <= intervals_a[i][end]
    print("\ta_overlaps_b: " + str(a_overlaps_b))
    print("\tb_overlaps_a: " + str(b_overlaps_a))
    
    # store the the intersection part
    if (a_overlaps_b or b_overlaps_a):
      print("\t\toverlap found: adding interval to the result")
      result.append([max(intervals_a[i][start], intervals_b[j][start]), min(
        intervals_a[i][end], intervals_b[j][end])])
      print("\t\tresult: " + str(result))
    else:
      print("\t\toverlap not found")
    # move next from the interval which is finishing first
    if intervals_a[i][end] < intervals_b[j][end]:
      i += 1
    else:
      j += 1
  return result
def main():
  intervals = [[[[1, 3], [5, 6], [7, 9]], [[2, 3], [5, 7]]],
              [[[1, 3], [5, 7], [9, 12]], [[5, 10]]]]
  for i in range(len(intervals)):
    print("Find intersecting intervals for: ")
    print("\tintervals 1: " + str(intervals[i][0]))
    print("\tintervals 2: " + str(intervals[i][1]))
    print("\nIntersecting intervals: " + str(merge(intervals[i][0],intervals[i][1])) + "\n")
    print("-"*100+"\n")
main()