Interval & Sweepline
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[][]{};
List<int[]> list = new ArrayList<>();
Arrays.sort(intervals, new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
// if (a[0] == b[0]) return a[1] - b[1];
return a[0] - b[0];
}
});
int start = intervals[0][0], end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
int[] in = intervals[i];
if (in[0] > end) {
list.add(new int[]{start, end});
start = in[0];
end = in[1];
} else {
end = Math.max(end, in[1]);
}
}
list.add(new int[]{start, end});
int[][] res = new int[list.size()][2];
for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
return res;
}public int[][] insert(int[][] intervals, int[] newInterval) {
int i = 0;
int n = intervals.length;
// if ()
List<int[]> res = new ArrayList<>();
while (i < n && intervals[i][1] < newInterval[0]) {
res.add(intervals[i++]);
}
int start = newInterval[0];
int end = newInterval[1];
while (i < n && end >= intervals[i][0]) {
start = Math.min(start, intervals[i][0]);
end = Math.max(end, intervals[i][1]);
i++;
}
res.add(new int[]{start, end});
// i++;
while (i < n) res.add(intervals[i++]);
int[][] result = new int[res.size()][2];
for (int k = 0; k < res.size(); k++) result[k] = res.get(k);
return result;
}Use capacity to keep track of the capacity on the vehicle. The capacity is reduced when adding passengers, and the capacity is increased when release passengers. When capacity < 0, return false.
Sort the trips by start location, and loop over the trips. Use a PriorityQueue and rank by end location to extract the earliest ended trips. Release capacity of those ended trips, and check valid.
public boolean carPooling(int[][] trips, int capacity) {
Arrays.sort(trips, new Comparator<>() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
PriorityQueue<int[]> pq
= new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a, int [] b) {
return a[2] - b[2];
}
});
for (int[] trip : trips) {
while (!pq.isEmpty() && pq.peek()[2] <= trip[1]) {
capacity += pq.poll()[0];
}
capacity -= trip[0];
if (capacity < 0) return false;
pq.offer(trip);
}
return true;
} public int countOfAirplanes(List<Interval> airplanes) {
Collections.sort(airplanes, (Interval o1, Interval o2) -> o1.start - o2.start);
int count = 0, max = 0;
PriorityQueue<Interval> pq = new PriorityQueue<>(
(Interval o1, Interval o2) -> o1.end - o2.end);
for (Interval in : airplanes) {
if (!pq.isEmpty() && pq.peek().end <= in.start) {
pq.poll();
}
pq.offer(in);
}
return pq.size();
}Sort and determine it the prev and curt interval has overlap.
public boolean canAttendMeetings(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return true;
}
Arrays.sort(intervals, (int[] in1, int[] in2) -> in1[0] - in2[0]);
int[] prev = intervals[0];
for (int i = 1; i < intervals.length; i++) {
int[] curt = intervals[i];
if (curt[0] < prev[1]) {
return false;
}
prev = curt;
}
return true;
}Sort the intervals by start time, use Heap(PQ) to sort by end time. Loop over all intervals, detect if the latest ended meeting in heap has overlap between the current meeting.
if yes, add curt to heap
otherwise extend the previous meeting in heap.
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
if (a[0] == b[0]) return a[1] - b[1];
return a[0] - b[0]; // sort by start
}
});
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
if (a[1] == b[1]) return a[0] - b[0];
return a[1] - b[1]; // sort by end
}
});
for (int[] curt : intervals) {
if (pq.isEmpty() || pq.peek()[1] > curt[0]) {
pq.offer(curt);
} else {
int[] prev = pq.poll();
pq.offer(new int[]{prev[0], curt[1]});
}
}
return pq.size();
}TreeMap:
public int minMeetingRooms(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int[] in : intervals) {
map.put(in[0], map.getOrDefault(in[0], 0) + 1);
map.put(in[1], map.getOrDefault(in[1], 0) - 1);
}
int count = 0, max = 0;
for (int key : map.keySet()) {
count += map.get(key);
max = Math.max(max, count);
}
return max;
}class MyCalendar {
TreeMap<Integer, Integer> map;
public MyCalendar() {
map = new TreeMap<>();
}
public boolean book(int start, int end) {
Integer lowerKey = map.floorKey(start);
Integer hiKey = map.higherKey(start);
if ((lowerKey != null && map.get(lowerKey) > start)
|| (hiKey != null && hiKey < end)) {
return false;
}
map.put(start, end);
return true;
}
}Use two lists to store intervals, if there is an existing overlap, then add the overlap portion to the next list. When adding a new interval, check if there is a overlap with the second list.
List<int[]> list;
List<int[]> overlap;
public MyCalendarTwo() {
list = new ArrayList<>();
overlap = new ArrayList<>();
}
public boolean book(int start, int end) {
for (int[] o : overlap) {
if (o[0] < end && o[1] > start) {
return false;
}
}
for (int[] o : list) {
if (o[0] < end && o[1] > start) {
overlap.add(new int[]{Math.max(o[0], start),
Math.min(o[1], end)});
}
}
list.add(new int[]{start, end});
return true;
}TreeMap sweepline
class MyCalendarThree {
TreeMap<Integer, Integer> treeMap;
public MyCalendarThree() {
treeMap = new TreeMap<>();
}
public int book(int start, int end) {
treeMap.put(start, treeMap.getOrDefault(start, 0) + 1);
treeMap.put(end, treeMap.getOrDefault(end, 0) - 1);
int ongoing = 0;
int k = 0;
for (int value : treeMap.values()) {
k = Math.max(ongoing += value, k);
}
return k;
}
}Sort the balloons by end coordinate
x_end.Initiate the end coordinate of a balloon which ends first:
first_end = points[0][1].Initiate the number of arrows:
arrows = 1.Iterate over all balloons:
If the balloon starts after
first_end:Increase the number of arrows by one.
Set
first_endto be equal to the end of the current balloon.
Return arrows.
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.size() == 0) return 0;
sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b){
return a[1] < b[1];
});
int arrow = 1;
int start = points[0][0], end = points[0][1];
for (int i = 1; i < points.size(); ++i) {
int curtStart = points[i][0];
int curtEnd = points[i][1];
if (curtStart > end) {
arrow++;
end = max(end, curtEnd);
}
}
return arrow;
}
};public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (a[0] == b[0]) return a[1] - b[1];
return a[0] - b[0];
}
}) ;
int prev = 0;
int count = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[prev][1]) { // overlap
if (intervals[i][1] < intervals[prev][1]) prev = i;
count++;
} else {
prev = i;
}
}
return count;
}Sort the slots by starting time. Use two pointers and calculate the overlap between two slots, if overlap >= duration, return the result. Move the pointer with earlier starting time.
public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
Arrays.sort(slots1, (a,b)->a[0]-b[0]); // sort increasing by start time
Arrays.sort(slots2, (a,b)->a[0]-b[0]); // sort increasing by start time
int i = 0, j = 0;
List<Integer> res = new ArrayList<>();
while (i < slots1.length && j < slots2.length) {
int overlap = Math.min(slots1[i][1], slots2[j][1]) - Math.max(slots1[i][0], slots2[j][0]);
if (overlap >= duration) {
res.add(Math.max(slots1[i][0], slots2[j][0]));
res.add(Math.max(slots1[i][0], slots2[j][0]) + duration);
break;
}
if (slots1[i][1] < slots2[j][1]) {
i++;
} else {
j++;
}
}
return res;
} public List<Interval> employeeFreeTime(List<List<Interval>> avails) {
List<Interval> result = new ArrayList<>();
List<Interval> list = new ArrayList<>();
for (List<Interval> l : schedule) {
list.addAll(l);
}
Collections.sort(list, (o1, o2) -> (o1.start - o2.start));
List<Interval> res = new ArrayList<>();
int start = list.get(0).start, end = list.get(0).end;
for (int i = 1; i < list.size(); i++) {
Interval curt = list.get(i);
if (end >= curt.start) {
end = Math.max(end, curt.end);
} else {
res.add(new Interval(end, curt.start));
start = curt.start;
end = curt.end;
}
}
return res;
}class Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
vector<Interval> intervals;
for (const vector<Interval> v : schedule) {
for (const Interval in : v) {
intervals.push_back(in);
}
}
sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b){
return a.start < b.start;
});
vector<Interval> gaps;
int start = intervals[0].start;
int end = intervals[0].end;
for (int i = 1; i < intervals.size(); ++i) {
int curtStart = intervals[i].start;
int curtEnd = intervals[i].end;
if (curtStart <= end) {
end = max(end, curtEnd);
} else {
gaps.emplace_back(Interval(end, curtStart));
start = curtStart;
end = curtEnd;
}
}
return gaps;
}
};Store all number ranges in a TreeMap and detect if there is an overlap or extension.
/** Initialize your data structure here. */
TreeMap<Integer, Integer> map;
public SummaryRanges() {
map = new TreeMap<>();
}
public void addNum(int val) {
if (map.containsKey(val)) return;
if (map.size() == 0) {
map.put(val, val);
} else if (map.lowerKey(val) != null && map.get(map.lowerKey(val)) == val - 1
&& map.higherKey(val) != null && map.higherKey(val) == val + 1) {
int histart = map.higherKey(val);
int hiend = map.get(histart);
map.put(map.lowerKey(val), hiend);
map.remove(histart);
} else if (map.lowerKey(val) != null && map.get(map.lowerKey(val)) >= val - 1) {
map.put(map.lowerKey(val), Math.max(val, map.get(map.lowerKey(val))));
} else if (map.higherKey(val) != null && map.higherKey(val) == val + 1) {
int histart = map.higherKey(val);
int hiend = map.get(histart);
map.put(val, hiend);
map.remove(histart);
} else {
map.put(val, val);
}
}
public int[][] getIntervals() {
int[][] res = new int[map.size()][2];
int i = 0;
Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, Integer> next = (Map.Entry<Integer, Integer>) it.next();
res[i++] = new int[]{next.getKey(), next.getValue()};
}
return res;
}Store all ranges in a TreeMap and detect the ones that overlap, starts with the floorKey then higherKey.
TreeMap<Integer, Integer> map;
public RangeModule() {
map = new TreeMap<>();
}
public void addRange(int left, int right) {
Integer floorKey = map.floorKey(left);
if (floorKey != null) {
int prevLeft = floorKey, prevRight = map.get(floorKey);
if (left <= prevRight) {
left = Math.min(left, prevLeft);
right = Math.max(right, prevRight);
}
}
map.put(left, right);
Integer higherKey = map.higherKey(left);
while (higherKey != null && higherKey <= right) {
right = Math.max(map.get(higherKey), right);
map.remove(higherKey);
map.put(left, right);
higherKey = map.higherKey(left);
}
}
public boolean queryRange(int left, int right) {
Integer floorKey = map.floorKey(left);
return floorKey != null && map.get(floorKey) >= right;
}
public void removeRange(int left, int right) {
addRange(left, right);
Integer floorKey = map.floorKey(left);
int left1 = floorKey, right2 = map.get(floorKey);
int right1 = left, left2 = right;
map.remove(floorKey);
if (left1 < right1) { map.put(left1, right1); }
if (left2 < right2) { map.put(left2, right2); }
}3355. Zero Array Transformation I
function isZeroArray(nums: number[], queries: number[][]): boolean {
const n = nums.length;
const deltaArray: number[] = new Array(n + 1).fill(0);
for (const [left, right] of queries) {
deltaArray[left] += 1;
if (right + 1 <= n - 1) {
deltaArray[right + 1] -= 1;
}
}
let currentOperations = 0;
for (let i = 0; i < n; i++) {
currentOperations += deltaArray[i];
if (currentOperations < nums[i]) {
return false;
}
}
return true;
}
1288. Remove Covered Intervals
sort by starting time, if starting time equals, the interval end last ranks to the front
if next end <= prev end, means overlap, count the number of overlaps
update prevEnd if no overlap
class Solution {
public:
int removeCoveredIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
if (a[0] == b[0]) {
return a[1] > b[1];
}
return a[0] < b[0];
});
int count = 0;
int prevEnd = intervals[0][1];
for (int i = 1; i < intervals.size(); ++i) {
// if
if (intervals[i][1] <= prevEnd) {
count++;
} else {
prevEnd = intervals[i][1];
}
}
return intervals.size() - count;
}
};3439. Reschedule Meetings for Maximum Free Time I
You're given the total duration of an event and multiple smaller events with their respective start and end times. The goal is to determine the maximum total free time that can be obtained by selecting k + 1 non-overlapping gaps between the events.
Approach
First, compute the gaps between the events:
Gap before the first event:
startTime[0]Gaps between events:
startTime[i] - endTime[i - 1]Gap after the last event:
eventTime - endTime[n - 1]
We store these gaps in a vector
gapof sizen + 1.Then, apply a sliding window of size
k + 1to find the maximum sum of anyk + 1contiguous gaps.
class Solution {
public:
int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
int n = startTime.size();
vector<int> gaps(n + 1, 0);
for (int i = 0; i < n; ++i) {
if (i == 0) {
gaps[i] = startTime[i];
} else {
gaps[i] = startTime[i] - endTime[i - 1];
}
}
gaps[n] = eventTime - endTime[n - 1];
int res = 0, sum = 0;
for (int R = 0, L = 0; R <= n; ++R) {
sum += gaps[R];
if (R - L > k) { // keep a k size window
sum -= gaps[L++];
}
res = max(res, sum);
}
return res;
}
};LeetCode Solution: Maximum Free Time by Event Manipulation
Problem Overview Given:
eventTime: Total available time durationstartTime[]andendTime[]: Arrays defining scheduled events
Objective: Maximize continuous free time by strategically moving or removing one event to merge adjacent time gaps.
Visual Demo
Example: eventTime = 12, Events: [1,3], [4,6], [9,11]
eventTime = 12, Events: [1,3], [4,6], [9,11]Initial Timeline:
0 1 2 3 4 5 6 7 8 9 10 11 12
|---|███████|---|███████|---|---|---|███████|---|
gap1 evt1 gap2 evt2 gap3 evt3 gap4
1 2 1 2 3 2 1Gaps: [1, 1, 3, 1] (before evt1, between evt1-evt2, between evt2-evt3, after evt3)
Strategy 1: Move Event
Move Event 2 (duration=2) to fit in Gap 3 (size=3):
Before:
|---|███████|---|███████|---|---|---|███████|---|
evt1 evt2 gap3 evt3
After moving evt2 to gap3:
|---|███████|---|---|---|███████|███|███████|---|
evt1 merged gap evt2 evt3
(1 + 2 + 0 = 3)Result: Combined free time = 3 units
Strategy 2: Remove Event
Remove Event 2 entirely:
Before:
|---|███████|---|███████|---|---|---|███████|---|
evt1 evt2 gap3 evt3
After removing evt2:
|---|███████|---|---|---|---|---|---|███████|---|
evt1 merged gap evt3
(1 + 2 + 3 = 6)Result: Combined free time = 6 units
Algorithm Breakdown
1. Gap Calculation
gaps = [1, 1, 3, 1] // [before_first, between_events..., after_last]2. Right-Side Maximum Tracking
maxR = [3, 1, 1, 0] // max gap to the right of each position3. Event Processing
For each event i:
Can move? Check if
event_duration ≤ max(maxL, maxR[i])Move strategy:
result = gap[i-1] + duration + gap[i]Remove strategy:
result = gap[i-1] + gap[i]
4. Example Walkthrough
Event 1: duration=2, maxL=0, maxR[1]=1
- Can't move (2 > max(0,1))
- Remove: gaps[0] + gaps[1] = 1 + 1 = 2
Event 2: duration=2, maxL=1, maxR[2]=1
- Can't move (2 > max(1,1))
- Remove: gaps[1] + gaps[2] = 1 + 3 = 4
Event 3: duration=2, maxL=1, maxR[3]=0
- Can't move (2 > max(1,0))
- Remove: gaps[2] + gaps[3] = 3 + 1 = 4Maximum Result: 4 units of continuous free time
Key Insights
Event relocation works only when destination gap ≥ event duration
Event removal always merges adjacent gaps
Optimal strategy depends on gap sizes and event durations
Greedy approach considers both options for each event position
Time Complexity: O(n) | Space Complexity: O(n)
class Solution {
public:
int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
int n = startTime.size();
// Calculate gaps between consecutive meetings
vector<int> gaps(n + 1, 0);
for (int i = 0; i < n; ++i) {
if (i == 0) {
gaps[i] = startTime[i]; // Gap before first meeting
} else {
gaps[i] = startTime[i] - endTime[i - 1]; // Gap between meetings
}
}
gaps[n] = eventTime - endTime[n - 1]; // Gap after last meeting
// maxR[i] = maximum gap to the right of position i
vector<int> maxR(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
maxR[i] = max(maxR[i + 1], gaps[i + 1]);
}
int maxL = 0; // Maximum gap to the left up to current position
int res = 0;
for (int i = 1; i <= n; ++i) {
int duration = endTime[i - 1] - startTime[i - 1];
// Check if we can move current meeting to left or right gap
if (maxL >= duration || maxR[i] >= duration) {
// Combine adjacent gaps by moving the meeting
res = max(res, gaps[i - 1] + duration + gaps[i]);
// gap before + current meeting duration + gap after
}
// Alternative: Remove current meeting entirely and merge gaps
res = max(res, gaps[i - 1] + gaps[i]);
// This means: no suitable place to move meeting, so remove it
// and combine the two adjacent gaps: -M- becomes ---
// where M = meeting, - = gap
maxL = max(maxL, gaps[i - 1]); // Update maximum left gap
}
return res;
}
};Last updated
Was this helpful?