> For the complete documentation index, see [llms.txt](https://howardyangemail.gitbook.io/decode-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://howardyangemail.gitbook.io/decode-leetcode/array/interval.md).

# Interval & Sweepline

#### [56. Merge Intervals](https://leetcode.com/problems/merge-intervals/)

```java
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;
}
```

#### [57. Insert Interval](https://leetcode.com/problems/insert-interval/)

```java
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;
}
```

#### [1094. Car Pooling](https://leetcode.com/problems/car-pooling/)

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.&#x20;

```java
    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;
    }
```

#### [391. Number of Airplanes in the Sky (lintcode)](https://www.lintcode.com/problem/number-of-airplanes-in-the-sky/description)

{% tabs %}
{% tab title="Java" %}

```java
    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();
    }
```

{% endtab %}

{% tab title="Java (TreeMap)" %}

```java
    public int countOfAirplanes(List<Interval> airplanes) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (Interval interval : airplanes) {
            map.put(interval.start, map.getOrDefault(interval.start, 0) + 1);
            map.put(interval.end, map.getOrDefault(interval.end, 0) - 1);
        }
        int count = 0, max = 0;
        for (int key : map.keySet()) {
            count += map.get(key);
            max = Math.max(max, count);
        }
        return max;
    }
```

{% endtab %}
{% endtabs %}

#### [252. Meeting Rooms](https://leetcode.com/problems/meeting-rooms/)

Sort and determine it the `prev` and `curt` interval has overlap.

```java
    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;
    }
```

#### [253. Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/)

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.

```java
    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:

```java
    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;
    }
```

#### [729. My Calendar I](https://leetcode.com/problems/my-calendar-i/)

```java
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;
    }
}
```

#### [731. My Calendar II](https://leetcode.com/problems/my-calendar-ii/)

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.

```java
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;
}
```

#### [732. My Calendar III](https://leetcode.com/problems/my-calendar-iii/)

TreeMap sweepline

```java
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;
    }
}
```

#### [452. Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/)

* 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_end` to be equal to the end of the current balloon.
* Return arrows.

```cpp
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;
    }
};
```

#### [435. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/)

```java
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;
}
```

#### [1229. Meeting Scheduler](https://leetcode.com/problems/meeting-scheduler/)

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.

```java
    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;
    }
```

#### [759. Employee Free Time](https://leetcode.com/problems/employee-free-time/)

```java
    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;
    }
```

```cpp
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;
    }
};
```

#### [352. Data Stream as Disjoint Intervals](https://leetcode.com/problems/data-stream-as-disjoint-intervals/)

Store all number ranges in a TreeMap and detect if there is an overlap or extension.

```java
/** 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;
}
```

#### [715. Range Module](https://leetcode.com/problems/range-module/)

Store all ranges in a TreeMap and detect the ones that overlap, starts with the floorKey then higherKey.

```java
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](https://leetcode.com/problems/zero-array-transformation-i/)

```typescript
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](https://leetcode.com/problems/remove-covered-intervals/)

1. sort by starting time, if starting time equals, the interval end last ranks to the front
2. if next end <= prev end, means overlap, count the number of overlaps
3. update prevEnd if no overlap

```cpp
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](https://leetcode.com/problems/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

1. 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]`
2. We store these gaps in a vector `gap` of size `n + 1`.
3. Then, apply a **sliding window** of size `k + 1` to find the maximum sum of any `k + 1` contiguous gaps.

```cpp
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;
    }
};
```

#### [3440. Reschedule Meetings for Maximum Free Time II](https://leetcode.com/problems/reschedule-meetings-for-maximum-free-time-ii/)

**LeetCode Solution: Maximum Free Time by Event Manipulation**

**Problem Overview** Given:

* `eventTime`: Total available time duration
* `startTime[]` and `endTime[]`: 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]`

**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     1
```

**Gaps**: `[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**

```cpp
gaps = [1, 1, 3, 1]  // [before_first, between_events..., after_last]
```

#### **2. Right-Side Maximum Tracking**

```cpp
maxR = [3, 1, 1, 0]  // max gap to the right of each position
```

#### **3. 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 = 4
```

**Maximum 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)

```cpp
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;
    }
};
```