Last active 5 days ago

Interview prep notes

linkjobai revised this gist 5 days ago. Go to revision

1 file changed, 46 insertions

meetingrooms.md(file created)

@@ -0,0 +1,46 @@
1 + # Interval Problems: Meeting Rooms I and II
2 +
3 + Interval questions come up constantly because they test sorting, greedy reasoning and heaps all at once.
4 +
5 + ## Meeting Rooms I (can one person attend all meetings?)
6 +
7 + Sort by start time and check whether any meeting starts before the previous one ends.
8 +
9 + ```python
10 + def can_attend(intervals):
11 + intervals.sort()
12 + return all(intervals[i][0] >= intervals[i-1][1]
13 + for i in range(1, len(intervals)))
14 + ```
15 +
16 + ## Meeting Rooms II (minimum number of rooms)
17 +
18 + Sort by start; keep a min-heap of end times for rooms in use. If the earliest-ending room is free when the next meeting starts, reuse it.
19 +
20 + ```python
21 + import heapq
22 + def min_rooms(intervals):
23 + intervals.sort()
24 + ends = []
25 + for s, e in intervals:
26 + if ends and ends[0] <= s:
27 + heapq.heapreplace(ends, e)
28 + else:
29 + heapq.heappush(ends, e)
30 + return len(ends)
31 + ```
32 +
33 + O(n log n) time. An equally good alternative is a **sweep line**: sort all starts and all ends separately, walk both with two pointers, and track the maximum number of meetings open at once.
34 +
35 + ## Clarify the boundary
36 +
37 + Does a meeting ending at 10:00 conflict with one starting at 10:00? Usually no, hence `<=` above, but ask the interviewer. It's an easy way to show care.
38 +
39 + ## Related problems
40 +
41 + - Merge Intervals (56): sort, then extend or append.
42 + - Non-overlapping Intervals (435): greedy by *end* time, counting removals.
43 + - Insert Interval (57) and Employee Free Time (759).
44 +
45 + ---
46 + *Disclosure: I'm on the team behind [Linkjob AI](https://www.linkjob.ai/coding-interview-copilot/), a coding interview assistant.*
Newer Older