Minimizing Workload Gaps - codepath/compsci_guides GitHub Wiki

Unit 4 Session 2 Standard (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the goal of the problem?
  • A: The goal is to find the smallest gap in minutes between any two consecutive work sessions.
• Q: What are the inputs?
  • A: The input is a list of tuples, where each tuple represents a work session with a start and end time in 24-hour format (e.g., 1300 for 1:00 PM).
• Q: What are the outputs?
  • A: The output is an integer representing the smallest gap in minutes between any two consecutive work sessions.
• Q: How is the time represented?
  • A: Time is represented in 24-hour format as integers (e.g., 1300 for 1:00 PM).
• Q: Can work sessions overlap?
  • A: No, it is assumed that work sessions do not overlap.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: First, convert the session times into minutes from the start of the day. Then, sort the sessions by start time. Iterate through the sorted list and calculate the gap between the end of one session and the start of the next. Track the smallest gap found.

1) Define a helper function `convert_to_minutes(time)` to convert 24-hour time format to minutes since midnight.
2) Sort the `work_sessions` list by the start time of each session.
3) Initialize a variable `smallest_gap` to infinity.
4) Iterate through the sorted list from the second element:
   a) Calculate the end time of the previous session in minutes.
   b) Calculate the start time of the current session in minutes.
   c) Compute the gap between the two.
   d) If this gap is smaller than `smallest_gap`, update `smallest_gap`.
5) Return the `smallest_gap`.

**⚠️ Common Mistakes**

- Forgetting to sort the work sessions by start time before finding gaps.
- Not correctly converting the time from 24-hour format to minutes.
- Assuming the smallest gap should be a positive number; if sessions are continuous, the gap can be zero.

I-mplement

def convert_to_minutes(time):
    hours = time // 100
    minutes = time % 100
    return hours * 60 + minutes

def find_smallest_gap(work_sessions):
    # Sort the work sessions based on start times
    work_sessions.sort()

    smallest_gap = float('inf')

    for i in range(1, len(work_sessions)):
        # Calculate the end time of the previous session and the start time of the current session
        end_time_prev = convert_to_minutes(work_sessions[i-1][1])
        start_time_curr = convert_to_minutes(work_sessions[i][0])

        # Calculate the gap between the end of the previous session and the start of the current session
        gap = start_time_curr - end_time_prev

        # Update the smallest gap found
        if gap < smallest_gap:
            smallest_gap = gap

    return smallest_gap

Example Usage:

work_sessions = [(900, 1100), (1300, 1500), (1600, 1800)]
print(find_smallest_gap(work_sessions))  # Output: 60

work_sessions_2 = [(1000, 1130), (1200, 1300), (1400, 1500)]
print(find_smallest_gap(work_sessions_2))  # Output: 30

work_sessions_3 = [(900, 1100), (1115, 1300), (1315, 1500)]
print(find_smallest_gap(work_sessions_3))  # Output: 15