> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/greedy_algorithm/meeting-rooms.md). # Meeting Rooms ## Question 1 ([LC.252](https://leetcode.com/problems/meeting-rooms/description/)) > Given an array of time intervals, determine if there's no overlap. ## Example ``` I: [[0,30],[5,10],[15,20]] O: false I: [[7,10],[2,4]] O: true ``` ## Approach An overlap can happen when the start time of the next meeting is before the end time of the current meeting. Sort by the start time. Check if the current meeting start time collides with the end time in the previous meeting. ## Code ```java public boolean canAttendMeetings(Interval[] meetings) { // edge check if (meetings == null || meetings.length <= 1) { return true; } // sort by start time Arrays.sort(meetings, (Interval i1, Interval i2) -> i1.start - i2.start); // check schedule conflict for (int i = 1; i < meetings.length; i++) { if (meetings[i].start < meetings[i-1].end) { return false; } } return true; } ``` ## Complexity Time O(nlogn) Space O(1) ## Question 2 ([LC.253](https://leetcode.com/problems/meeting-rooms-ii/description/)) > Given a list of time intervals `[[start_i, end_i], ..., [start_n, end_n]]`, find the minimum number of conferences rooms to hold all the meetings. ## Example ``` I: [[0, 30],[5, 10],[15, 20]] O: 3 I: [[7,10],[2,4]] O: 1 ``` Notice the input is not sorted. ## Sweep Line We can visualize this question as the picture below. ![](/files/-LtpqYFbLY5IQFZSC7gT) Intuitively, we want to somehow sort the meetings and find the maximum number of overlaps at some point.\ The line-sweep algorithm is designed to find intersections between intervals (1D) or rectangles (2D). A brute force attempt would be to scan the entire timeline in some unit of time (i.e. in minutes) and check the overlapping of meetings at each point of time. But `O(number of minutes)` is very expensive. Is there any way to reduce the computational complexity? We don't have to scan the time frame between two events (i.e. start of a meeting, start of another meeting). Because in that time frame, the number of conference rooms stay the same. In fact, the start and the end of a meeting are the only two events that count. Therefore, we can scan these two types of events instead of the entire timeline. If we visualize a vertical line that sweeps from left to right, at each event, the intersection count will increase by 1 when the line encounters the start of an interval and decrease by 1 when the line encounters the end of an interval. The sorting order will be ascending in time regardless of the type of the event nor the name of the meeting. ## Approach ``` Step 1 Create the list of events from the list of meetings Step 2 Sort the list of events Step 3 Sweep (scan) the sorted list of events and count the number of intersections Maintain a max count Step 4 Return the max ``` ## Code ```java private class Event { int time; boolean isStart; Event(int time, boolean isStart) { this.time = time; this.isStart = isStart; } } public int minMeetingRooms(List meetings) { // edge check if (meetings == null || meetings.size() == 0) { return 0; } // Step 1 Create a list of events List events = new ArrayList<>(); // meetings.size() * 2 for (Interval meeting : meetings) { events.add(new Event(meeting.start, true)); events.add(new Event(meeting.end, false)); } // Step 2 Sort events Comparator eventComp = new Comparator(){ // negative is less than, zero is equal, positive is greater than public int compare(Event e1, Event e2) { // we want to put the end time first so we don't increase the count if (e1.time == e2.time) { return Boolean.compare(e1.isStart, e2.isStart); } else { return e1.time - e2.time; } } }; Collections.sort(events, eventComp); // Step 3 Sweep the sorted list of events int maxIntersections = 0; int intersections = 0; for (Event event : events) { if (event.isStart) { intersections++; } else { intersections--; } maxIntersections = Math.max(maxIntersections, intersections); } return maxIntersections; } ``` ```python # sweep line algo # scan from left to right # start and end time as events # store in BST or even easier just a counter def minMeetingRooms(self, intervals: List[List[int]]) -> int: n = len(intervals) if n == 0: return 0 events: List[Tuple[int, int]] = [] for interval in intervals: events.append((interval[0], 1)) events.append((interval[1], -1)) # sort by meeting time then by event type sorted_events = sorted(events) intersections = 0 rooms = 0 for event in sorted_events: intersections += event[1] rooms = max(rooms, intersections) return rooms ``` ## Complexity Time O(nlogn) + O(n) Space O(n) ## Greedy Approach Alternatively, we can try greedy since this is a minimization problem on a sequence. First, we want to sort the meetings by start time (or symmetrically by end time). We can model each conference room as an interval that keeps a start time and an end time. We want to put the next meeting in the conference room with the smallest end time. If the smallest end time is bigger than the start time of next meeting, we need to create a new conference room. One way to prove the optimality of a greedy algorithm is to show that at every step there is no better approach than making a greedy choice locally. We can induct on the number of conference rooms. Suppose $$n^{th}$$ conference needs to be created for the current meeting $$\[start\_i, end\_i]$$. If we need to add a new conference room, then every existing conference room has a schedule conflict with the current meeting. We have $$n-1$$ meetings collide with the current meeting at time $$start\_i$$. This is true because the meetings are sorted by their start time (i.e. a gap then a meeting later is not possible). Regardless of what strategies we use, *at least* we need $$n$$ conferences. ## Code ```java public int minMeetingRooms(Interval[] meetings) { // edge check if (meetings == null || meetings.length == 0) { return 0; } // sort by starting time Arrays.sort(meetings, (Interval i1, Interval i2) -> i1.start - i2.start); // create a priority queue of conference room finish times PriorityQueue minHeap = new PriorityQueue(); minHeap.offer(meetings[0].end); for (int i = 1; i < meetings.length; i++) { // need an extra conference room if (minHeap.peek() > meetings[i].start) { minHeap.offer(meetings[i].end); } else { // can fit in an existing room minHeap.poll(); minHeap.offer(meetings[i].end); } } return minHeap.size(); } ``` Question: What if interval with different sizes have the same starting time? (i.e. a long meeting and a short meeting both start at 10). We don't care because the starting time alone can guarantee the optimality of this greedy algorithm. Note: In Java 8, Comparator is a functional interface. It can accept lambda expression for its compare method. ## Complexity Time O(nlogn) Space O(n) ## Time Intersection Variant A variant from Meeting Rooms II is to return all the intersection time between two lists of meetings. The brute force approach is still to scan the entire timeline and find overlaps. The better approach is to sweep the events (disregard which list they are from) and store the intervals that are intercepted (from 2 start events until the next end event). ## References * Top Coder [Line Sweep Algorithm](https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/) * MIT 6.046 [Recitation 6 Notes](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/recitation-notes/MIT6_046JS15_Recitation6.pdf) * Oreilly [What’s new in Java 8](https://www.oreilly.com/learning/whats-new-in-java-8-lambdas) * Java Doc Interface [Comparator](https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#compare-T-T-) --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://zedive.gitbook.io/project-l/part-2/greedy_algorithm/meeting-rooms.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.