Interval & Sweepline

56. Merge Intervals

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

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

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

391. Number of Airplanes in the Sky (lintcode)

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

Java (TreeMap)

252. Meeting Rooms

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

253. 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.

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

729. My Calendar I

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

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

732. My Calendar III

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

452. 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.

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

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

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

759. Employee Free Time

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

352. Data Stream as Disjoint Intervals

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

715. Range Module

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

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

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

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.

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

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

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

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