Insert Interval
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int n = intervals.size();
vector<vector<int>> res;
int i = 0;
while (i < n && intervals[i][1] < newInterval[0]) {
res.push_back(intervals[i++]);
}
// Merges overlapping intervals
int start = newInterval[0], end = newInterval[1];
while (i < n && intervals[i][0] <= end) {
start = min(start, intervals[i][0]);
end = max(end, intervals[i][1]);
i++;
}
res.push_back({start, end});
while (i < n) {
res.push_back(intervals[i++]);
}
return res;
}
|
TreeMap
Falling Squares
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public List<Integer> fallingSquares(int[][] positions) {
// start : height
TreeMap<Integer, Integer> map = new TreeMap<>();
// avoids null floor keys
map.put(0, 0);
List<Integer> list = new ArrayList<>();
int max = 0;
for (int[] p : positions) {
int start = p[0], end = start + p[1];
Integer from = map.floorKey(start);
int height = map.subMap(from, end)
.values()
.stream()
.max(Integer::compare)
.get() + p[1];
max = Math.max(max, height);
list.add(max);
// sets [start, end) to height
// sets [end, ) to prev
// prev is the height right before end before the current square is fallen
int prev = map.floorEntry(end).getValue();
map.put(start, height);
map.put(end, prev);
// removes intervals within (start, end)
map.subMap(start, false, end, false).clear();
}
return list;
}
|
We can also leverage Segment Tree to solve the problem. See Segment Tree.
Count Integers in Intervals
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class CountIntervals {
// {start : end}
private TreeMap<Integer, Integer> map = new TreeMap<>();
private int count = 0;
public CountIntervals() {
}
public void add(int left, int right) {
// processes floor interval
var f = map.floorEntry(left);
if (f != null && f.getValue() >= left) {
// updates left and right ends of the current interval
left = f.getKey();
right = Math.max(right, f.getValue());
// removes the floor interval
count -= f.getValue() - f.getKey() + 1;
map.remove(f.getKey());
}
// processes intervals between floor and ceiling
var subMap = map.subMap(left, false, right, true);
for (var e : subMap.entrySet()) {
right = Math.max(right, e.getValue());
count -= e.getValue() - e.getKey() + 1;
}
subMap.clear();
// adds the new interval
map.put(left, right);
count += right - left + 1;
}
public int count() {
return count;
}
}
|
Interval Overlapping Problem
Grouping overlapping intervals
Count Ways to Group Overlapping Ranges
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| private static final int MOD = (int)1e9 + 7;
public int countWays(int[][] ranges) {
Arrays.sort(ranges, Comparator.comparingInt(a -> a[0]));
int end = -1, ways = 1;
// greedily adds this range to the current group
for (int[] r : ranges) {
if (r[0] > end) {
// groups++;
ways = ways * 2 % MOD;
}
end = Math.max(end, r[1]);
}
return ways;
}
|
Check if All the Integers in a Range Are Covered
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public boolean isCovered(int[][] ranges, int left, int right) {
Arrays.sort(ranges, Comparator.comparingInt(r -> r[0]));
for (int[] r : ranges) {
if (left >= r[0] && left <= r[1]) {
// [left, r[1]] is covered
left = r[1] + 1;
// now left is the first integer that's uncovered
}
}
return left > right;
}
|
Remove Covered Intervals
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int removeCoveredIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int remaining = 0, end = -1;
for (int[] i : intervals) {
// if i[1] <= end, then i is covered by the range [i'[0], end]
// where i' is the interval when `remaining` was last incremented
if (i[1] > end) {
remaining++;
end = i[1];
}
}
return remaining;
}
|
BFS
The problems in this section have close connection with Jump Game II in Implicit BFS.
Video Stitching
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int videoStitching(int[][] clips, int time) {
int[] nums = new int[time + 1];
for (int[] clip : clips) {
if (clip[0] <= time) {
nums[clip[0]] = Math.max(nums[clip[0]], clip[1] - clip[0]);
}
}
return jump(nums);
}
// 45. Jump Game II
private int jump(int[] nums) {
}
|
Or, without the auxilliary array, we sort clips and rewrite the implicit BFS:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int videoStitching(int[][] clips, int time) {
Arrays.sort(clips, (a, b) -> a[0] - b[0]);
int index = 0, curr = 0, next = 0, res = 0;
while (curr < time) {
while (index < clips.length && clips[index][0] <= curr) {
next = Math.max(next, clips[index++][1]);
}
// this level didn't move forward
if (curr == next) {
return -1;
}
curr = next;
res++;
}
return res;
}
|
Minimum Number of Taps to Open to Water a Garden
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int minTaps(int n, int[] ranges) {
// uses j to denote the rightmost end of the area starting from i that can be watered by taps so far
// then arr[i] == j - i
int[] arr = new int[n + 1];
for (int i = 0; i <= n; i++) {
int left = Math.max(0, i - ranges[i]);
arr[left] = Math.max(arr[left], i + ranges[i] - left);
}
return jump(nums);
}
// 45. Jump Game II
private int jump(int[] nums) {
}
|
Interval Scheduling
Interval Scheduling Maximization Problem (ISMP)
ISMP: find a largest compatible set - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible.
Unweighted
Non-overlapping Intervals
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int eraseOverlapIntervals(int[][] intervals) {
// earliest deadline first (EDF) scheduling
// greedy
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
// iterates from left to right:
// if two intervals overlap, they belong to the same group
int end = intervals[0][1], groups = 1;
for (int[] i : intervals) {
if (i[0] >= end) {
end = i[1];
groups++;
}
}
return intervals.length - groups;
}
|
Maximum Number of Non-Overlapping Substrings
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| public List<String> maxNumOfSubstrings(String s) {
int n = s.length();
// {start, end}, n
int[][] intervals = new int[2][26];
Arrays.fill(intervals[0], n);
List<String> list = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'a';
intervals[0][index] = Math.min(intervals[0][index], i);
intervals[1][index] = i;
}
int end = -1;
for (int i = 0; i < n; i++) {
if (intervals[0][s.charAt(i) - 'a'] == i) {
int newEnd = updateEnd(s, i, intervals);
if (newEnd != -1) {
// a new valid string which doesn't overlap the previous valid string
if (i > end) {
list.add("");
}
// updates the last valid string with shorter inner string
// e.g. "abccba" -> "bccb" -> "cc"
end = newEnd;
list.set(list.size() - 1, s.substring(i, end + 1));
}
}
}
return list;
}
private int updateEnd(String s, int i, int[][] intervals) {
int end = intervals[1][s.charAt(i) - 'a'];
for (int j = i; j <= end; j++) {
// if a character appears before i
// so the string starting at i is invalid
if (intervals[0][s.charAt(j) - 'a'] < i) {
return -1;
}
end = Math.max(end, intervals[1][s.charAt(j) - 'a']);
}
return end;
}
|
Weighted
Maximum Profit in Job Scheduling
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size();
vector<int> indices(n);
iota(indices.begin(), indices.end(), 0);
// Sorts index by end time
ranges::sort(indices, {}, [&](int i){ return endTime[i]; });
// <end time, max profit>
map<int, int> dp = {{0, 0}};
for (int i : indices) {
// Curr is the max profit if we pick the current job.
// Binary searches in dp for the max profit we can make before startTime[i].
int curr = prev(dp.upper_bound(startTime[i]))->second + profit[i];
// If curr max profit is more than last time, it's worth doing this job.
// It guarantees the map value monotonically increases with endTime (keys).
if (curr > dp.rbegin()->second) {
dp[endTime[i]] = curr;
}
// Otherwise don't do this job.
}
return dp.rbegin()->second;
}
|
Maximize the Profit as the Salesman
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int maximizeTheProfit(int n, List<List<Integer>> offers) {
// end : list of index
Map<Integer, List<Integer>> map = new HashMap<>();
int[] dp = new int[n + 1];
for (int i = 0; i < offers.size(); i++) {
map.computeIfAbsent(offers.get(i).get(1), k -> new ArrayList<>()).add(i);
}
for (int i = 0; i < n; i++) {
dp[i + 1] = dp[i];
for (var e : map.getOrDefault(i, Collections.emptyList())) {
var o = offers.get(e);
dp[i + 1] = Math.max(dp[i + 1], dp[o.get(0)] + o.get(2));
}
}
return dp[n];
}
|
Maximum Number of Events That Can Be Attended II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public int maxValue(int[][] events, int k) {
// sorts events by end day
Arrays.sort(events, Comparator.comparingInt(e -> e[1]));
int n = events.length;
// end day : max sum
// rolling dp
// dp1: i - 1
// dp2: i
TreeMap<Integer, Integer> dp1 = new TreeMap<>(), dp2 = new TreeMap<>();
dp1.put(0, 0);
dp2.put(0, 0);
for (int i = 0; i < k; i++) {
for (int[] e : events) {
int sum = dp1.lowerEntry(e[0]).getValue();
if (sum + e[2] > dp2.lastEntry().getValue()) {
dp2.put(e[1], sum + e[2]);
}
}
dp1 = dp2;
dp2 = new TreeMap<>();
dp2.put(0, 0);
}
return dp1.lastEntry().getValue();
}
|
Merge Intervals
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> list = new ArrayList<>();
for (int[] i : intervals) {
if (list.isEmpty() || list.get(list.size() - 1)[1] < i[0]) {
list.add(i);
} else {
list.get(list.size() - 1)[1] = Math.max(list.get(list.size() - 1)[1], i[1]);
}
}
return list.toArray(new int[0][]);
}
|
Interval List Intersections
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> list = new ArrayList<>();
int i = 0, j = 0;
while (i < firstList.length && j < secondList.length) {
int start = Math.max(firstList[i][0], secondList[j][0]);
int end = Math.min(firstList[i][1], secondList[j][1]);
// intersects
if (start <= end) {
list.add(new int[]{start, end});
}
// removes the interval with the smallest endpoint
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return list.toArray(new int[0][]);
}
|
Minimum Number of Arrows to Burst Balloons
1
2
3
4
5
6
7
8
9
10
11
12
13
| int findMinArrowShots(vector<vector<int>>& points) {
// Sorts points by end coordinate
ranges::sort(points, {}, [&](vector<int>& p) { return p[1]; });
int arrow = points[0][1], cnt = 1;
for (const auto& point : points) {
if (arrow < point[0]) {
cnt++;
arrow = point[1];
}
}
return cnt;
}
|
The typical approach of this type of problem is to use a Priority Queue to record the current state at each timestamp. As time flows, the Priority Queue removes or adds elements. The idea is very similar to Sliding window.
Meeting Rooms II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int minMeetingRooms(int[][] intervals) {
// sorts invervals by start time
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// stores the end time of current open meetings in ascending order
Queue<Integer> pq = new PriorityQueue<>();
for (int[] interval : intervals) {
// frees up one old room if it's already ended
if (!pq.isEmpty() && interval[0] >= pq.peek()) {
pq.poll();
}
// occupies the spared old room or a new room
pq.offer(interval[1]);
}
// queue size is monotonically increasing
return pq.size();
}
|
Notice how similar it is to finding max length with upper bounded constraint by Sliding window - the window never shrinks.
Another solution is Line weep. We consolidate the number of occupied rooms at each time and find the max.
Same problem: Divide Intervals Into Minimum Number of Groups
Maximum Number of Events That Can Be Attended
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public int maxEvents(int[][] events) {
// sorts events by start day
Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
// stores the end day of the current open events
Queue<Integer> pq = new PriorityQueue<>();
int n = events.length, i = 0, count = 0, day = 0;
while (!pq.isEmpty() || i < n) {
// if no events are open on this day,
// flies time to the start day of the next open event
if (pq.isEmpty()) {
day = events[i][0];
}
// adds new events that can be attended on this day
while (i < n && events[i][0] <= day) {
pq.offer(events[i++][1]);
}
// attends the event that will end the earliest
pq.poll();
count++;
day++;
// removes closed events
while (!pq.isEmpty() && pq.peek() < day) {
pq.poll();
}
}
return count;
}
|
Maximum Number of Eaten Apples
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public int eatenApples(int[] apples, int[] days) {
// apple, end day
Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
int count = 0;
for (int i = 0; i < apples.length || !pq.isEmpty(); i++) {
// adds apples grown on the i-th day in a bag
if (i < apples.length) {
pq.offer(new int[]{apples[i], i + days[i]});
}
// removes rotten apples
while (!pq.isEmpty() && pq.peek()[1] <= i) {
pq.poll();
}
// gets the earliest available apple
if (!pq.isEmpty()) {
count++;
// removes if no apples left in the bag
if (--pq.peek()[0] == 0) {
pq.poll();
}
}
}
return count;
}
|
Course Schedule III
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public int scheduleCourse(int[][] courses) {
// sorts by deadlines (greedy)
Arrays.sort(courses, (a, b) -> a[1] - b[1]);
// duration
// once a course fits in, it can be removed any time later;
// and the other courses that have been added into the heap would still fit
Queue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
int time = 0;
for (int[] c : courses) {
// adds current course
time += c[0];
pq.offer(c[0]);
// if time exceeds, removes the heap top
if (time > c[1]) {
time -= pq.poll();
}
}
return pq.size();
}
|
Minimum Interval to Include Each Query
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| public int[] minInterval(int[][] intervals, int[] queries) {
// {size, end}
// we can use priority queue as well
TreeMap<Integer, Integer> map = new TreeMap<>();
// sorts intervals
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
// sorts queries index mapping array
int n = intervals.length, m = queries.length;
Integer[] indices = new Integer[m];
for (int i = 0; i < m; i++) {
indices[i] = i;
}
Arrays.sort(indices, Comparator.comparingInt(i -> queries[i]));
int j = 0; // index of current interval
int[] ans = new int[m];
// scans through queries in order
for (int i : indices) {
// enqueues
while (j < n && intervals[j][0] <= queries[i]) {
map.put(intervals[j][1] - intervals[j][0] + 1, intervals[j][1]);
j++;
}
// dequeues
while (!map.isEmpty() && map.firstEntry().getValue() < queries[i]) {
map.pollFirstEntry();
}
ans[i] = map.isEmpty() ? -1 : map.firstKey();
}
return ans;
}
|
It’s a useful trick to sort offline queries befre processing them.
Amount of New Area Painted Each Day
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public int[] amountPainted(int[][] paint) {
int n = paint.length;
int max = Arrays.stream(paint).mapToInt(p -> p[1]).max().getAsInt();
// area[i]: end of continuous painted area starting at i
int[] area = new int[max + 1], worklog = new int[n];
for (int i = 0; i < n; i++) {
int start = paint[i][0], end = paint[i][1];
while (start < end) {
// next position of the brush
int jump = 0;
// if the area is empty (area[start] == 0), jumps one step forward
if (area[start] == 0) {
jump = start + 1;
worklog[i]++;
} else {
// jumps to the end of existing painted area
jump = area[start];
}
// updates the end of the painted area starting from current `start`
if (end > area[start]) {
area[start] = end;
}
start = jump;
}
}
return worklog;
}
|
Maximum Distance in Arrays
1
2
3
4
5
6
7
8
9
10
11
| public int maxDistance(List<List<Integer>> arrays) {
int distance = 0, max = arrays.get(0).get(arrays.get(0).size() - 1), min = arrays.get(0).get(0);
for (int i = 1; i < arrays.size(); i++) {
distance = Math.max(Math.max(distance, Math.abs(arrays.get(i).get(0) - max)), Math.abs(arrays.get(i).get(arrays.get(i).size() - 1) - min));
max = Math.max(max, arrays.get(i).get(arrays.get(i).size() - 1));
min = Math.min(min, arrays.get(i).get(0));
}
return distance;
}
|
Set Intersection Size At Least Two
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public int intersectionSizeTwo(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
// the largest two elements in the the minimal set so far
int second = -2, largest = -1;
// compares the two elements with intervals[i]
// with this approach, size of S is minimized,
// and the largest two elements in S are maximized
int size = 0;
for (int[] i : intervals) {
// both elements intersect with i
if (i[0] <= second) {
continue;
}
// largest element intersects with i
if (i[0] <= largest) {
size++;
second = largest;
largest = i[1];
} else {
// neither intersects with i
size += 2;
second = i[1] - 1;
largest = i[1];
}
}
return size;
}
|
Minimum Time to Complete All Tasks
Credits to @Foxtail (see here).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| // @Foxtail
public int findMinimumTime(int[][] tasks) {
// it's optimal to start each task as late as possible
// in this way, it's most likely to overlap with the following tasks
//
// initially, the latest start time (LST) of task[i] = end_i - duration_i + 1
// among a few tasks, the task with smallest LST should start first
Arrays.sort(tasks, Comparator.comparingInt(t -> t[0]));
// stores running tasks
Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
// min time during which the computer should be turned on
int turnedOnTime = 0;
for (int i = 0; i <= tasks.length; i++) {
// tasks[i][0] is the current time instant
//
// if top[0] represents the k-th task
// top[0] + turnedOnTime (at current time, i.e., `tasks[i][0]`)
// = lst(tasks[k]) + turnedOnTime at time tasks[k][0] + turnedOnTime at time tasks[i][0]
// = lst(tasks[k]) + increased turnedOnTime during [k, i]
//
// for top[0], this value represents its current time since enqueued
while (!pq.isEmpty() && (i == tasks.length || pq.peek()[0] + turnedOnTime < tasks[i][0])) {
int[] top = pq.peek();
if (top[0] + turnedOnTime > top[1]) {
// the task is completed
pq.poll();
} else { // top[0] + turnedOnTime < top[1] + 1
// delta = current turnedOnTime - previous turnedOnTime
// delta = Math.min(top[1] + 1, tasks[i][0]) - (top[0] + turnedOnTime)
// turnedOnTime += delta
//
// if top[i] < tasks[i][0], after this turnedOnTime change, the top will be popped
// otherwise, after this turnedOnTime change, exits the loop
turnedOnTime = Math.min(top[1] + 1, i == tasks.length ? Integer.MAX_VALUE : tasks[i][0]) - top[0];
}
}
if (i < tasks.length) {
// `- turnedOnTime` to "hide" this value at this time instant in the node
pq.offer(new int[]{tasks[i][1] - tasks[i][2] + 1 - turnedOnTime, tasks[i][1]});
}
}
return turnedOnTime;
}
|
Dynamic Programming
Video Stitching
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| private int MAX_NUM_CLIPS = 100;
public int videoStitching(int[][] clips, int time) {
Arrays.sort(clips, (a, b) -> a[0] - b[0]);
int[] dp = new int[time + 1];
Arrays.fill(dp, MAX_NUM_CLIPS + 1);
dp[0] = 0;
for (int[] c : clips) {
for (int i = c[0] + 1; i <= Math.min(time, c[1]); i++) {
dp[i] = Math.min(dp[i], dp[c[0]] + 1);
}
}
return dp[time] == MAX_NUM_CLIPS + 1 ? -1 : dp[time];
}
|
Intersection
Meeting Scheduler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
Arrays.sort(slots1, (a, b) -> a[0] - b[0]);
Arrays.sort(slots2, (a, b) -> a[0] - b[0]);
int i = 0, j = 0;
while (i < slots1.length && j < slots2.length) {
// finds the boundaries of the intersection
int left = Math.max(slots1[i][0], slots2[j][0]);
int right = Math.min(slots1[i][1], slots2[j][1]);
if (right - left >= duration) {
return Arrays.asList(left, left + duration);
}
// always moves the one that ends earlier
if (slots1[i][1] < slots2[j][1]) {
i++;
} else {
j++;
}
}
return Collections.EMPTY_LIST;
}
|
Data Structure
Seat Reservation Manager
1
2
3
4
5
6
7
8
9
10
11
12
13
| private Queue<Integer> unreserved = new PriorityQueue<>();
private int maxReserved = 0;
public SeatManager(int n) {
}
public int reserve() {
return unreserved.isEmpty() ? ++maxReserved : unreserved.poll();
}
public void unreserve(int seatNumber) {
unreserved.offer(seatNumber);
}
|
Range Module
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class RangeModule {
private TreeMap<Integer, Integer> intervals = new TreeMap<>(); // [left, right)
public RangeModule() {
}
public void addRange(int left, int right) {
Integer start = intervals.floorKey(left), end = intervals.floorKey(right);
// the current interval overlaps with start interval
if (start != null && intervals.get(start) >= left) {
left = start;
}
// the current interval overlaps with end interval
if (end != null && intervals.get(end) > right) {
right = intervals.get(end);
}
intervals.put(left, right);
// clears intervals in between
intervals.subMap(left, false, right, true).clear();
}
public boolean queryRange(int left, int right) {
Integer start = intervals.floorKey(left);
return start != null && intervals.get(start) >= right;
}
public void removeRange(int left, int right) {
Integer start = intervals.floorKey(left), end = intervals.floorKey(right);
// the current interval overlaps with end interval
if (end != null && intervals.get(end) > right) {
intervals.put(right, intervals.get(end));
}
// the current interval overlaps with start interval
// if start == end,
// this block could possibly override the right end of the interval,
// so this case must be handled after the above one.
// (notice right != start, so the above case won't impact this case)
if (start != null && intervals.get(start) > left) {
intervals.put(start, left);
}
// clears intervals in between
intervals.subMap(left, true, right, false).clear();
}
}
|
Exam Room
PriorityQueue:
1
2
3
4
5
6
7
| // {start, end, priority, isValid}
// isValid is for lazy deletion
Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> -a[2]));
// start: interval
// end: interval
Map<Integer, int[]> startMap, endMap;
|
TreeMap (no lazy deletion):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| private TreeSet<Interval> intervals = new TreeSet<>();
// start: end
// end: start
private Map<Integer, Integer> ends = new HashMap<>(), starts = new HashMap<>();
private int n;
public ExamRoom(int N) {
this.n = N;
intervals.add(new Interval(0, N - 1, n));
ends.put(0, N - 1);
starts.put(N - 1, 0);
}
// O(log(n))
public int seat() {
Interval i = intervals.pollLast();
int seat = i.getSeat();
intervals.add(new Interval(i.start, seat - 1, n));
intervals.add(new Interval(seat + 1, i.end, n));
ends.put(i.start, seat - 1);
starts.put(seat - 1, i.start);
ends.put(seat + 1, i.end);
starts.put(i.end, seat + 1);
return seat;
}
// O(log(n))
public void leave(int p) {
// gets the start of the interval on p's left
// gets the end of the interval on p's right
int start = starts.get(p - 1), end = ends.get(p + 1);
// merges p's adjacent intervals
intervals.remove(new Interval(start, p - 1, n));
intervals.remove(new Interval(p + 1, end, n));
intervals.add(new Interval(start, end, n));
ends.put(start, end);
starts.put(end, start);
starts.remove(p - 1);
ends.remove(p + 1);
}
class Interval implements Comparable<Interval> {
int n;
int start, end;
Interval(int start, int end, int n) {
this.start = start;
this.end = end;
this.n = n;
}
// takes distance as priority
int getPriority() {
// edge case: left end
if (start == 0) {
return end;
}
// edge case: right end
if (end == n - 1) {
return n - 1 - start;
}
// if interval size is 0,
// assigns lowest priority to it
if (end < start) {
return -1;
}
return (end - start) / 2;
}
int getSeat() {
if (start == 0) {
return 0;
}
if (end == n - 1) {
return n - 1;
}
return (start + end) >>> 1;
}
@Override
public int compareTo(Interval i) {
int p1 = getPriority(), p2 = i.getPriority();
// if priorities are equal, pick the lowest number
return p1 == p2 ? i.start - start : p1 - p2;
}
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Interval)) {
return false;
}
Interval interval = (Interval) o;
return start == interval.start &&
Objects.equals(end, interval.end) &&
Objects.equals(n, interval.n);
}
@Override
public int hashCode() {
return Objects.hash(start, end, n);
}
}
|