Meeting Rooms I
Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.
Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Sort intervals by start time and loop through them to check for any overlap
public boolean canAttendMeetings(int[][] intervals) {
Arrays.sort(intervals, (interval1, interval2) -> interval1[0]==interval2[0] ? interval1[1]-interval2[1] : interval1[0] - interval2[0]);
for(int index=1; index < intervals.length; index++) {
if (intervals[index][0] < intervals[index-1][1])
return false;
}
return true;
}
Meeting Rooms II
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Answer is the maximum number of meetings that are going on at the same time
Sort by start time, and go through the array by:
1. remove all the meetings that have ended from minHeap
2. add this meeting into the minHeap
3. check size of minHeap
if (intervals == null) return 0;
Arrays.sort(intervals, (interval1, interval2) -> interval1[0]==interval2[0] ? interval1[1]-interval2[1] : interval1[0] - interval2[0]);
int result = 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int index=0; index<intervals.length; index++) {
while(!minHeap.isEmpty() && minHeap.peek() <= intervals[index][0])
minHeap.poll();
minHeap.add(intervals[index][1]);
result = Math.max(minHeap.size(), result);
}
return result;</Integer>
Maximum Number of Events That Can Be Attended
You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.
You can attend an event i at any day d where startDayi <= d <= endDayi. You can only attend one event at any time d.
Return the maximum number of events you can attend.
Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.
Use a greedy strategy: if we can attend two events on the same day, prioritize the one will earlier end time
Store in minHeap all meetings that can be attended on each particular day
if (events == null) return 0;
Arrays.sort(events, (interval1, interval2) -> interval1[0]==interval2[0] ? interval1[1]-interval2[1] : interval1[0] - interval2[0]);
int maxDay = 0;
for(int[] event: events) {
maxDay = Math.max(maxDay, event[1]);
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int result = 0;
//count the days from the first day and see what can be attended then
for(int day=1, eventIndex=0; day<=maxDay; day++) {
while(eventIndex < events.length && events[eventIndex][0] <= day) {
minHeap.add(events[eventIndex][1]);
eventIndex++;
}
while(!minHeap.isEmpty() && minHeap.peek() < day)
minHeap.poll();
if (!minHeap.isEmpty()) {
minHeap.poll(); //attend this meeting
result++;
}
}
return result;
}</Integer>
Meeting Rooms III
You are given an integer n. There are n rooms numbered from 0 to n - 1.
You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.
Meetings are allocated to rooms in the following manner:
Each meeting will take place in the unused room with the lowest number.
If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
When a room becomes unused, meetings that have an earlier original start time should be given the room.
Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.
A half-closed interval [a, b) is the interval between a and b including a and not including b.
Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0.
Hold values:
1. number of meetings in room: new int[n]; Fill this in and pick the one with max value to return
2. currently unused rooms: a minHeap we poll from in order of earliest start time, and we pick it
If a room is not free for the current meeting, then we delay it until one becomes available.
2. Currently used rooms: a minHeap wrt end time, holds an array: <room number, end time of meeting>
var meetingCount = new int[n];
var usedRooms = new PriorityQueue<long[]>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
var unusedRooms = new PriorityQueue<Integer>();
for (int i = 0; i < n; i++) {
unusedRooms.offer(i);
}
Arrays.sort(meetings, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
for (int[] meeting : meetings) {
int start = meeting[0], end = meeting[1];
while (!usedRooms.isEmpty() && usedRooms.peek()[0] <= start) {
int room = (int) usedRooms.poll()[1];
unusedRooms.offer(room);
}
if (!unusedRooms.isEmpty()) {
int room = unusedRooms.poll();
usedRooms.offer(new long[]{end, room});
meetingCount[room]++;
} else {
long roomAvailabilityTime = usedRooms.peek()[0];
int room = (int) usedRooms.poll()[1];
usedRooms.offer(new long[]{roomAvailabilityTime + end - start, room});
meetingCount[room]++;
}
}
int maxMeetingCount = 0, maxMeetingCountRoom = 0;
for (int i = 0; i < n; i++) {
if (meetingCount[i] > maxMeetingCount) {
maxMeetingCount = meetingCount[i];
maxMeetingCountRoom = i;
}
}
return maxMeetingCountRoom;Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]
Deque<int[]> merged = new LinkedList<>();
if (intervals == null) return intervals;
Arrays.sort(intervals, (a, b) -> (a[0]==b[0] ? a[1]-b[1] : a[0]-b[0]));
for(int[] interval: intervals) {
if (merged.isEmpty() || merged.peekLast()[1] < interval[0]) {
merged.addLast(interval);
} else {
int[] mergedInterval = merged.pollLast();
mergedInterval[0] = Math.min(mergedInterval[0], interval[0]);
mergedInterval[1] = Math.max(mergedInterval[1], interval[1]);
merged.addLast(mergedInterval);
}
}
int[][] result = new int[merged.size()][2];
for(int index=0; index<result.length; index++) {
result[index] = merged.pollFirst();
}
return result;
High-Access Employees
You are given a 2D 0-indexed array of strings, access_times, with size n. For each i where 0 <= i <= n - 1, access_times[i][0] represents the name of an employee, and access_times[i][1] represents the access time of that employee. All entries in access_times are within the same day.
The access time is represented as four digits using a 24-hour time format, for example, “0800” or “2250”.
An employee is said to be high-access if he has accessed the system three or more times within a one-hour period.
Times with exactly one hour of difference are not considered part of the same one-hour period. For example, “0815” and “0915” are not part of the same one-hour period.
Access times at the start and end of the day are not counted within the same one-hour period. For example, “0005” and “2350” are not part of the same one-hour period.
Return a list that contains the names of high-access employees with any order you want.
Input: access_times = [[“a”,”0549”],[“b”,”0457”],[“a”,”0532”],[“a”,”0621”],[“b”,”0540”]]
Output: [“a”]
Explanation: “a” has three access times in the one-hour period of [05:32, 06:31] which are 05:32, 05:49, and 06:21.
But “b” does not have more than two access times at all.
So the answer is [“a”].
Group all employee access times using a hashmap.
Store times of access as minutes from midnight: HHMM becomes HH*60+MM, and then use those values, to add a user to high access list if any 3 consecutive values in sorted order are within <60 minutes of each other.
Use a list and then sort it as we can have two access at same time for some reason.
Map<String, List<Integer>> accessMap = new HashMap<>();
for(List<String> entry: access_times) {
String user = entry.get(0);
int time = Integer.parseInt(entry.get(1).substring(0, 2))*60 + Integer.parseInt(entry.get(1).substring(2, 4));
accessMap.putIfAbsent(user, new ArrayList<>());
accessMap.get(user).add(time);
}
List<String> result = new ArrayList<>();
for(String user: accessMap.keySet()) {
List<Integer> timeList = accessMap.get(user);
Collections.sort(timeList);
//check if any 3 consecutive ones are between 60 minutes
for(int index=2; index<timeList.size(); index++) {
if (timeList.get(index) - timeList.get(index-2) < 60) {
result.add(user);
break;
}
}
}
return result;Non-overlapping Intervals
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Sort by end times, and if there is a meeting with overlapping interval, greedily keep the one that ends first to try to make space for maximum others.
Arrays.sort(intervals, (i1, i2) -> i1[1]-i2[1]);
int lastIntervalEndTime = Integer.MIN_VALUE;
int result = intervals.length; //assume initially all to be returned
for(int[] interval: intervals) {
if (interval[0] >= lastIntervalEndTime) {
result--;
lastIntervalEndTime = interval[1];
}
}
return result;
