Meeting Rooms - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10-15 mins
• 🛠️ Topics: Sorting, Intervals, Greedy Algorithm

1: U-nderstand

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

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Can meetings overlap by sharing the same end and start time?

  • Yes, if one meeting ends at the same time another starts, they don’t overlap.

• Do we need to handle empty intervals?

  • If the input list is empty, return True since there are no meetings to attend.

HAPPY CASE
Input: intervals = [0,30],[5,10],[15,20](/codepath/compsci_guides/wiki/0,30],[5,10],[15,20)
Output: False
Explanation: The meetings [0,30] and [5,10] overlap.

Input: intervals = [7,10],[2,4](/codepath/compsci_guides/wiki/7,10],[2,4)
Output: True
Explanation: There are no overlapping meetings.

EDGE CASE
Input: intervals = []
Output: True
Explanation: No meetings to attend, so it’s possible to attend all.

Input: intervals = [1,2](/codepath/compsci_guides/wiki/1,2)
Output: True
Explanation: With a single meeting, it’s possible to attend it.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Interval Problems, we want to consider the following approaches:

• Sorting: Sort intervals by their start time to easily compare adjacent intervals for overlap.
• Greedy Approach: Check if any two consecutive intervals overlap after sorting.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: If any two meetings overlap, it’s not possible to attend all meetings. We can sort the intervals by their start times and check for overlap between consecutive meetings.

1) Sort the intervals based on the starting times.
2) Iterate over the sorted intervals from the second one to the end.
3) For each interval, check if its start time is less than the end time of the previous interval.
4) If overlap is found, return False.
5) If no overlap is found after checking all intervals, return True.

⚠️ Common Mistakes

• Not sorting the intervals before checking for overlap.
• Failing to handle edge cases such as empty input or a single interval.

4: I-mplement

Implement the code to solve the algorithm.

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])
    
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
    return True

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: intervals = [0,30],[5,10],15,20

  • Sorted Intervals: [0,30], [5,10], 15,20
  • Comparing [5,10] with [0,30]: Overlap found.
  • Output: False

• Input: intervals = [7,10],2,4

  • Sorted Intervals: [2,4], 7,10
  • No overlap found.
  • Output: True

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of intervals.

• Time Complexity: O(N log N) due to sorting the intervals.
• Space Complexity: O(1) as no additional space is used beyond a constant amount.