Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/253.html
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]] Output: 1
Constraints:
1 <= intervals.length <= 1040 <= starti < endi <= 106
TreeMap
What is the difference between a HashMap and a TreeMap? https://stackoverflow.com/questions/2444359/what-is-the-difference-between-a-hashmap-and-a-treemap/2444370
TreeMap is an example of a SortedMap, which means that the order of the keys can be sorted, and when iterating over the keys, you can expect that they will be in order.
HashMap on the other hand, makes no such guarantee. Therefore, when iterating over the keys of a HashMap, you can’t be sure what order they will be in.
HashMap will be more efficient in general, so use it whenever you don’t care about the order of the keys.
More ref: https://www.baeldung.com/java-treemap
// incremental
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString());
}
// reverse order
@Test
public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() {
TreeMap<Integer, String> map =
new TreeMap<>(Comparator.reverseOrder());
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString());
}
// Entry as element, customized comparator
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() {
SortedSet<Map.Entry<String, Double>> sortedset = new TreeSet<Map.Entry<String, Double>>(
new Comparator<Map.Entry<String, Double>>() {
@Override
public int compare(Map.Entry<String, Double> e1,
Map.Entry<String, Double> e2) {
return e1.getValue().compareTo(e2.getValue());
}
});
sortedset.addAll(myMap.entrySet());
}
// usage
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() {
TreeMap<String, String> map = new TreeMap<>();
map.put("c", "val");
map.put("b", "val");
map.put("a", "val");
map.put("e", "val");
map.put("d", "val");
assertEquals("[a, b, c, d, e]", map.keySet().toString());
}
// usage: max/min element
@Test
public void givenTreeMap_whenPerformsQueries_thenCorrect() {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
Integer highestKey = map.lastKey();
Integer lowestKey = map.firstKey();
Set<Integer> keysLessThan3 = map.headMap(3).keySet();
Set<Integer> keysGreaterThanEqTo3 = map.tailMap(3).keySet();
assertEquals(new Integer(5), highestKey);
assertEquals(new Integer(1), lowestKey);
assertEquals("[1, 2]", keysLessThan3.toString());
assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString());
}
or, utilize Java8 Lambda api stream() and sorted()
// core is how to sort the map by it's values, i.e., sort the map (movie->count) by counts
movieToCount = movieToCount.entrySet().stream()
.sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
Long mostViewedMovie = movieToCount.entrySet().iterator().next().getKey();
Algorithm
TreeMap
Traverse the time interval. For the start time, the mapping value is incremented by 1, and for the end time, the mapping value is decremented by 1.
Then define the result variable res, and the number of rooms rooms, traverse the TreeMap, time from small to large, add the mapping value to the number of rooms each time, and then update the result res. When the starting time is encountered, the mapping is positive, the number of rooms will increase.
If a time is the end time of one meeting and the start time of another meeting, the mapping value is decreased first and then increased and remains at 0, no new room is allocated, and the mapping value of the end time is a negative number and will not increase the number of rooms.
Heap
First sort all the time intervals according to the starting time, and then create a new minimum heap.
Start traversing the time interval. If the heap is not empty and the first element is less than or equal to the start time of the current interval, remove the first element from the heap and push the end time of the current interval into the heap.
Since the smallest heap is at the front, if the first element is less than or equal to the start time, it means that the previous meeting has ended and the meeting room can be used to start the next meeting, so there is no need to allocate a new meeting room. After the traversal is completed, the heap The number of elements is the number of meeting rooms needed.
Code
-
import java.util.Arrays; import java.util.PriorityQueue; import java.util.TreeMap; public class Meeting_Rooms_II { public static void main(String[] args) { Meeting_Rooms_II out = new Meeting_Rooms_II(); Solution_heap s = out.new Solution_heap(); System.out.println(s.minMeetingRooms( new Interval[]{ new Interval(0, 30), new Interval(5, 10), new Interval(15, 20) } )); // test solution 2 Solution_treemap sss = out.new Solution_treemap(); System.out.println(sss.minMeetingRooms( new Interval[]{ new Interval(0, 30), new Interval(5, 10), new Interval(15, 20) } )); } public class Solution_treemap { public int minMeetingRooms(Interval[] intervals) { TreeMap<Integer, Integer> m = new TreeMap<>(); for (Interval each: intervals) { int start = each.start; int end = each.end; m.put(start, 1 + m.getOrDefault(start, 0)); m.put(end, m.getOrDefault(end, 0) - 1); } int active = 0; int result = 0; // If a time is the end time of one meeting and the start time of another meeting, // the mapping value is decreased first and then increased and remains at 0, no new room is allocated for (int v: m.values()) { active += v; result = Math.max(result, active); } return result; } } public class Solution_heap { public int minMeetingRooms(Interval[] intervals) { if(intervals == null || intervals.length == 0) { return 0; } // Sort the intervals by start time Arrays.sort(intervals, (i1, i2) -> i1.start - i2.start); // to store end time of each meeting, smaller value will be at the peek() PriorityQueue<Integer> heap = new PriorityQueue<Integer>(); // start with the first meeting, put it to a meeting room int count = 1; heap.offer(intervals[0].end); for(int i = 1; i < intervals.length; i++){ if(intervals[i].start < heap.peek()) { count++; // conflict, need 1 more room heap.offer(intervals[i].end); // poll then offer, conceptually merging 2 intervals } else { // if the current meeting starts right after // there's no need for a new room, merge the interval heap.offer(Math.max(intervals[i].end, heap.poll())); // poll then offer, conceptually merging 2 intervals } } return count; } } } ############ class Solution { public int minMeetingRooms(int[][] intervals) { int n = 1000010; int[] delta = new int[n]; for (int[] e : intervals) { ++delta[e[0]]; --delta[e[1]]; } int res = delta[0]; for (int i = 1; i < n; ++i) { delta[i] += delta[i - 1]; res = Math.max(res, delta[i]); } return res; } } -
// OJ: https://leetcode.com/problems/meeting-rooms-ii/ // Time: O(NlogN) // Space: O(N) class Solution { public: int minMeetingRooms(vector<vector<int>>& A) { vector<int> starts, ends; for (auto &v : A) { starts.push_back(v[0]); ends.push_back(v[1]); } sort(begin(starts), end(starts)); sort(begin(ends), end(ends)); int N = A.size(), ans = 0, cnt = 0; for (int i = 0, j = 0; i < N;) { if (starts[i] < ends[j]) { ++cnt; ++i; ans = max(ans, cnt); } else if (starts[i] > ends[j]) { --cnt; ++j; } else { ++i; ++j; } } return ans; } }; -
''' data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8] list(accumulate(data, operator.mul)) # running product [3, 12, 72, 144, 144, 1296, 0, 0, 0, 0] list(accumulate(data, max)) # running maximum [3, 4, 6, 6, 6, 9, 9, 9, 9, 9] >>> from itertools import accumulate >>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8] >>> accumulate(data) <itertools.accumulate object at 0x10fd78440> >>> list(accumulate(data)) [3, 7, 13, 15, 16, 25, 25, 32, 37, 45] >>> max(accumulate(data)) 45 https://docs.python.org/3/library/itertools.html#itertools.accumulate # Amortize a 5% loan of 1000 with 4 annual payments of 90 cashflows = [1000, -90, -90, -90, -90] list(accumulate(cashflows, lambda bal, pmt: bal*1.05 + pmt)) [1000, 960.0, 918.0, 873.9000000000001, 827.5950000000001] ''' class Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int: delta = [0] * 1000010 for start, end in intervals: delta[start] += 1 delta[end] -= 1 return max(accumulate(delta)) ############ class Solution(object): def minMeetingRooms(self, intervals): """ :type intervals: List[Interval] :rtype: int """ meetings = [] for i in intervals: meetings.append((i.start, 1)) meetings.append((i.end, 0)) meetings.sort() ans = 0 count = 0 for meeting in meetings: if meeting[1] == 1: count += 1 else: count -= 1 ans = max(ans, count) return ans -
func minMeetingRooms(intervals [][]int) int { n := 1000010 delta := make([]int, n) for _, e := range intervals { delta[e[0]]++ delta[e[1]]-- } res := delta[0] for i := 1; i < n; i++ { delta[i] += delta[i-1] res = max(res, delta[i]) } return res } func max(a, b int) int { if a > b { return a } return b }