Unit 4 Session 2 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
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.
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