Finding Free Slots in Two People's Calendar (with python code and step by step code execution walkthrough)


1. Sorted Merge of Two Lists of Numbers

1.1 Algorithm Explanation

The sorted merge algorithm takes two sorted lists of numbers and merges them into a single sorted list. We use two pointers to keep track of the current element in each list and compare the elements to determine the order in the merged list.

1.2 Python Code


def merge_sorted_lists(list1, list2):
    merged_list = []
    i, j = 0, 0

    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            merged_list.append(list1[i])
            i += 1
        else:
            merged_list.append(list2[j])
            j += 1

    while i < len(list1):
        merged_list.append(list1[i])
        i += 1

    while j < len(list2):
        merged_list.append(list2[j])
        j += 1

    return merged_list

1.3 Example

Lists:

  • List 1: [1, 3, 5]
  • List 2: [2, 4, 6]

Merged List:


merged_list = merge_sorted_lists([1, 3, 5], [2, 4, 6])
print(merged_list)
# Output: [1, 2, 3, 4, 5, 6] 

1.4 Step-by-Step Execution

Iteration i j list1[i] list2[j] Merged List
1 0 0 1 2 [1]
2 1 0 3 2 [1, 2]
3 1 1 3 4 [1, 2, 3]
4 2 1 5 4 [1, 2, 3, 4]
5 2 2 5 6 [1, 2, 3, 4, 5]
6 3 2 - 6 [1, 2, 3, 4, 5, 6]
 

2. Merging Two Calendars

2.1 Algorithm Explanation

To merge two people's calendars, we represent the calendars as lists of tuples where each tuple represents a busy time slot. The algorithm merges these lists of tuples to find the common free slots.

2.2 Python Code


def merge_calendars(calendar1, calendar2):
    merged_calendar = []
    i, j = 0, 0

    while i < len(calendar1) and j < len(calendar2):
        if calendar1[i][0] < calendar2[j][0]:
            merged_calendar.append(calendar1[i])
            i += 1
        else:
            merged_calendar.append(calendar2[j])
            j += 1

    while i < len(calendar1):
        merged_calendar.append(calendar1[i])
        i += 1

    while j < len(calendar2):
        merged_calendar.append(calendar2[j])
        j += 1

    return merged_calendar

def find_free_slots(calendar1, calendar2, working_hours):
    merged_calendar = merge_calendars(calendar1, calendar2)
    free_slots = []
    end_of_last_meeting = working_hours[0]

    for meeting in merged_calendar:
        if end_of_last_meeting < meeting[0]:
            free_slots.append((end_of_last_meeting, meeting[0]))
        end_of_last_meeting = max(end_of_last_meeting, meeting[1])

    if end_of_last_meeting < working_hours[1]:
        free_slots.append((end_of_last_meeting, working_hours[1]))

    return free_slots

2.3 Example

Calendars:
  • Calendar 1: [(9, 10), (12, 13), (16, 17)]
  • Calendar 2: [(10, 11), (13, 14), (15, 16)]
  • Working Hours: (9, 18)

Free Slots:

free_slots = find_free_slots([(9, 10), (12, 13), (16, 17)], [(10, 11), (13, 14), (15, 16)], (9, 18)) print(free_slots) # Output: [(11, 12), (14, 15), (17, 18)]

2.4 Step-by-Step Execution

Iteration i j calendar1[i] calendar2[j] Merged Calendar
1 0 0 (9, 10) (10, 11) [(9, 10)]
2 1 0 (12, 13) (10, 11) [(9, 10), (10, 11)]
3 1 1 (12, 13) (13, 14) [(9, 10), (10, 11), (12, 13)]
4 2 1 (16, 17) (13, 14) [(9, 10), (10, 11), (12, 13), (13, 14)]
5 2 2 (16, 17) (15, 16) [(9, 10), (10, 11), (12, 13), (13, 14), (15, 16)]
6 2 3 (16, 17) - [(9, 10), (10, 11), (12, 13), (13, 14), (15, 16), (16, 17)]

3. Merging Two Calendars with Single Traversal of Two People's Calendar

3.1 Algorithm Explanation

To optimize the merging process, we can traverse both calendars simultaneously and merge them in a single pass. This approach reduces the number of iterations needed compared to merging them separately and then processing the merged list.

3.2 Python Code


def find_free_slots_single_traversal(calendar1, calendar2, working_hours):
    i, j = 0, 0
    free_slots = []
    end_of_last_meeting = working_hours[0]

    while i < len(calendar1) and j < len(calendar2):
        if calendar1[i][0] < calendar2[j][0]:
            current_meeting = calendar1[i]
            i += 1
        else:
            current_meeting = calendar2[j]
            j += 1
        
        if end_of_last_meeting < current_meeting[0]:
            free_slots.append((end_of_last_meeting, current_meeting[0]))
        end_of_last_meeting = max(end_of_last_meeting, current_meeting[1])

    while i < len(calendar1):
        current_meeting = calendar1[i]
        if end_of_last_meeting < current_meeting[0]:
            free_slots.append((end_of_last_meeting, current_meeting[0]))
        end_of_last_meeting = max(end_of_last_meeting, current_meeting[1])
        i += 1

    while j < len(calendar2):
        current_meeting = calendar2[j]
        if end_of_last_meeting < current_meeting[0]:
            free_slots.append((end_of_last_meeting, current_meeting[0]))
        end_of_last_meeting = max(end_of_last_meeting, current_meeting[1])
        j += 1

    if end_of_last_meeting < working_hours[1]:
        free_slots.append((end_of_last_meeting, working_hours[1]))

    return free_slots

3.3 Example

Calendars:

  • Calendar 1: [(9, 10), (12, 13), (16, 17)]
  • Calendar 2: [(10, 11), (13, 14), (15, 16)]
  • Working Hours: (9, 18)

Free Slots:


free_slots = find_free_slots_single_traversal([(9, 10), (12, 13), (16, 17)], [(10, 11), (13, 14), (15, 16)], (9, 18))
print(free_slots)
# Output: [(11, 12), (14, 15), (17, 18)]

3.4 Step-by-Step Execution

It follows similar iterations to the ones in section 2.4

4. Summary: From Simple Merge to Finding Free Slots in Calendars

4.1 Simple Merge of Two Lists

Algorithm Explanation:

  • We started by merging two sorted lists of numbers into a single sorted list.
  • We used two pointers (i and j) to keep track of the current element in each list.
  • We compared the elements from both lists and added the smaller element to the merged list.
  • After processing all elements from one list, we added the remaining elements from the other list.

4.2 Merging Two Calendars

Algorithm Explanation:

  • We represented the calendars as lists of tuples, where each tuple represents a busy time slot.
  • We merged these lists of tuples using a similar approach to the simple merge.
  • We then identified the gaps between meetings as free slots.

4.3 Merging Two Calendars with Single Traversal

Algorithm Explanation:

  • To optimize the merging process, we traversed both calendars simultaneously and merged them in a single pass.
  • This approach reduced the number of iterations needed compared to merging them separately and then processing the merged list.

Explanation:

  • Single Traversal: We traversed both calendars simultaneously, comparing the current meeting slots from both calendars and adding the earlier one to the merged calendar.
  • Finding Free Slots: We identified gaps between meetings in the single traversal and added them as free slots.

Above section provided a summary of how we built a simple merge of two lists, extended the concept to find free slots in two people's calendars, and further optimized the process with a single traversal.

Support Our Efforts and Earn Together ðŸš€

Visit https://parucodes.github.io/ today and start your journey to becoming a fast, accurate, and confident touch typist.

If you find our website useful and want to support us, consider joining the exciting world of Bitcoin mining on your mobile phone. Follow this link: Mine PI Bitcoin and use my username prarthanadp as your invitation code. With the referral code prarthanadp, you'll receive a special referral bonus.

Thank you for your support! Let's grow and earn together! 🌟

 

Comments

Post a Comment

Popular posts from this blog

Recursion examples for Beginners (step by step code execution walkthrough with python code)

  Factorial Explanation and Example Factorial Definition: The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It can be defined recursively as: factorial(0) = 1 (Base Case) factorial(n) = n * factorial(n-1) (Recursive Case) +----------------------------------+ | factorial(n) | | +---------------------------+ | | Base Case: | | | factorial(0) = 1 | | +---------------------------+ | | Recursive Case: | | | factorial(n) = n * | | | factorial(n-1)| | +---------------------------+ +----------------------------------+ Python Code for Factorial def factorial(n): if n == 0: return 1 else: return n * factorial(n - 1) # Example Usage print(factorial(5...
Read more

Handling hierarchical Data using Dictionaries for beginners (with python code)

  Handling Hierarchical Data with Python Dictionaries 1. Introduction to Hierarchical Data Hierarchical data is organized into a tree-like structure with different levels of depth. Each level contains unique objects that are connected to objects in the level above. This type of data is common in various domains, such as organizational structures, file systems, and biological classifications. 2. Example Data We'll create a 5-level hierarchical data structure. The data represents an organizational hierarchy with departments, teams, managers, employees, and tasks. data = { "Department1": { "TeamA": { "Manager1": { "Employee1": { "Task1": "Complete report", "Task2": "Attend meeting" }, "Employee2": { "Task1": "Write...
Read more

Word Search in Maze using Depth First Search (with python code and step by step code execution walkthrough)

  1. Introduction In this blog, we will explain how to solve the word search problem in a maze using Depth First Search (DFS) algorithm. We will use a 3x3 maze and search for the word 'the' in the maze. The word 'the' is located in the second row of the maze. 2. Algorithm Explanation The DFS algorithm is used to explore all possible paths in the maze to find the target word. We start from each cell in the maze and recursively explore its neighbors to find the word. 2.1 Steps of the Algorithm Start from each cell in the maze. Check if the current cell matches the current character of the word. Mark the current cell as visited. Recursively explore the neighboring cells (up, down, left, right). Unmark the current cell and backtrack if the word is not found. Return true if the word is found, otherwise return false. 3. Python Code def dfs(maze, word, i, j, index): if index == len(word): return True if i < 0 or i >= len(maze) or j < 0 or j >= len(...
Read more