Neetcode 150 — Intervals

最近為了練習刷題，開始寫 Neetcode 150。以下是我的刷題筆記，主要以 JAVA 來練習，分類及題目來自 Neetcode。

Note

1. 合併 interval 三步驟：比 new interval 小的，和 new interval 重疊的，比 new interval 大的，例如第一題，第二題
2. 移除最少數目來避免重疊：根據 end 來排序，增加後面可以接的 interval 數量，例如第三題
3. 排 meeting：根據 start 排序，但是否 meeting 能接在 meeting 之後，要看 end，可用 minHeap 來放 end，例如第四題，第五題
4. query 要在 length 最短的 interval：可把適合區間的 interval 放進 minnHeap，minHeap sort by length，利如第六題

1. Insert Interval

// 1. Brute Force
// 題目會給一串排序過的 interval，並且不會彼此重疊。
// 現在要加上一段新的 interval，如果有和先前的 interval 重疊需要合併。
// Input: intervals = [[1,3],[4,6]], newInterval = [2,5]
// 可以把 new Interval for loop 原本 intervals 一遍，如果重疊就合併成 newInterval；
// 最後再把 newInterval 插到正確的位置
//
// 假設 interval 有 n 個
// Time complexity: O(n)
// Space complexity: O(n)
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> tmpResult = new ArrayList<>();
        for (int[] interval : intervals) {
            if (newInterval[1] < interval[0] || newInterval[0] > interval[1]) {
                tmpResult.add(interval);
            } else {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            }
        }
        int[][] result = new int[tmpResult.size() + 1][2];
        int i = 0;
        boolean added = false;
        for (int[] interval : tmpResult) {
            if (!added && newInterval[0] < interval[0]) {
                result[i] = newInterval;
                added = true;
                i++;
            }
            result[i] = interval;
            i++;
        }
        if (!added) {
            result[i] = newInterval;
        }
        return result;
    }
}
// 2. 三階段寫法
// Step1: 比 newInterval 小的
// Step2: 合併重疊的，newInterval[0]>=intervals[1]&&interval[0]<=newInterval[1]
// Step3: 比 newInterval 大的
//
// Time complexity: O(n)
// Space complexity: O(n)
//
// Dry run
// intervals = [[1,2], [3,5], [6,7], [8,10], [12,16]], newInterval = [4,9]
// Step1: 比 newInterval 小的
// [1,2] -> 2 < 4, result=[[1,2]]
// [3,5] -> 5 沒有 < 4
// Step2: 重疊的
// [3,5] -> 3 <= 9, newInterval = [3,9]
// [6,7] -> 6 <= 9, newInterval = [3,9]
// [8,10] -> 8 <= 9, newInterval = [3,10]
// [12,16] -> 12 沒有 <= 10
// result=[[1,2],[3,10]]
// Step3: 比 newInterval 大的
// [12,16] -> result=[[1,2],[3,10],[12,16]]
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }
        while (i < intervals.length && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        result.add(newInterval);
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }
        return result.toArray(new int[result.size()][]);
    }
}

Get AShiou’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

2. Merge Intervals

// 1. 
// 給一連串的 interval，把重疊的合併起來
// for loop intervals，沒有重疊就放進結果，有重疊就和結果的最後一個合併
//
// 假設 intervals 有 n 個
// Time complexity: O(nlogn + n) -> O(nlogn)
// Space complexity: O(n)
// 
// Dry run
// intervals = [[1,3],[1,5],[6,7]]
// sort: [[1,3],[1,5],[6,7]]
// [1,3] -> result:[1,3]
// [1,5] -> 1 < 3, result:[[1,5]]
// [6,7] -> 6 沒有小於 5, result:[[1,5],[6,7]]
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            if (!result.isEmpty() && intervals[i][0] <= result.get(result.size() - 1)[1]) {
                result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], intervals[i][1]);
            } else {
                result.add(intervals[i]);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

3. Non-overlapping Intervals

// 1. Greedy
// 給一連串的 interval，把部分重疊的刪除，來達到沒有重複，目標是刪除最少數量的 interval
// 原本的想法是根據 start 時間 sort，在重疊時刪除 interval 較長的
// 但最正確的做法是重複時，刪除 end 時間較後面的，要保留 end 時間較前面的讓後面更有空間塞更多 interval
// ex. 
// [58, 95]  // length = 37
// [66, 98]  // length = 32
// [82, 97]  // length = 15
// [95, 99]  // length = 4
// 照我原本的想法，重疊時刪除較長的，會變成留下[95, 99]
// 刪除 end 時間較後面的，會留下[58, 95], [95, 99]
//
// 假設有 n 個 interval
// Time complexity: O(nlogn+n) -> O(n)
// Space complexity: O(1)
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length < 2) {
            return 0;
        }
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[] prev = new int[2];
        prev[0] = intervals[0][0];
        prev[1] = intervals[0][1];
        int removed = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < prev[1]) {
                if (intervals[i][1] < prev[1]) {
                    prev[0] = intervals[i][0];
                    prev[1] = intervals[i][1];
                }
                removed++;
            } else {
                prev[0] = intervals[i][0];
                prev[1] = intervals[i][1];
            }
        }
        return removed;
    }
}
// 2. sort by end time 更直覺
// 只需要紀錄 end 的時間
//
// Time complexity: O(nlogn)
// Space complexity: O(1)
//
// Dry run
// intervals = [[1,2],[2,4],[1,4]]
// sort: [[1,2],[2,4],[1,4]]
// [1,2] -> prevEnd = 2
// [2,4] -> prevEnd = 4
// [1,4] -> removed = 1
//
// intervals = [[58, 95],[66,98],[82,97],[95,99]]
// sort: [[58, 95],[82,97],[66,98],[95,99]]
// [58,95] -> prevEnd=95
// [82,97] -> 82 < 95, removed=1
// [66,98] -> 66 < 95, removed=2
// [95,99] -> prevEnd=99
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length < 2) {
            return 0;
        }
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int removed = 0;
        int prevEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < prevEnd) {
                removed++;
            } else {
                prevEnd = intervals[i][1];
            }
        }
        return removed;
    }
}

4. Meeting Rooms

// 1. sort 
// 檢查是否有 interval 重複，
// 最簡單的方式是先根據 start time sort，然後跟前一個 interval 比對是否有重複
//
// 假設有 n 個 interval
// Time complexity: O(nlogn + n) -> O(nlogn)
// Space complexity: O(1)
//
// Dry run
// intervals = [(0,30),(5,10),(15,20)]
// sort: [(0,30),(5,10),(15,20)]
// (0,30)
// (5,10) -> 5 < 30, return false
/**
 * Definition of Interval:
 * public class Interval {
 *     public int start, end;
 *     public Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
class Solution {
    public boolean canAttendMeetings(List<Interval> intervals) {
        intervals.sort((a, b) -> a.start - b.start);
        int prevEnd = Integer.MIN_VALUE;
        for (Interval interval : intervals) {
            if (interval.start < prevEnd) {
                return false;
            }
            prevEnd = interval.end;
        }
        return true;
    }
}

5. Meeting Rooms II

// 1.
// 有多個 interval，如果 interval 重複，代表需要另一間會議室，需要算出最多需要幾間房間
// sort by start time，用一個 minHeap 紀錄目前的房間，minHeap 只需紀錄 end time
// 遇到一個 interval，如果 end time > start time，就需要再加一個房間
//
// 假設有 n 個 interval，開 k 個房間
// Time complexity: O(nlogn + nlogk) -> O(nlogn)
// Space complexity: O(k)
// 
// Dry run
// intervals = [(0,40),(5,10),(15,20)]
// sort: [(0,40),(5,10),(15,20)]
// (0,40) -> minHeap:[40]
// (5,10) -> 40 沒有 <= 10, minHeap:[10,40]
// (15,20) -> 10 <= 20, minHeap:[20,40]
// return 2
/**
 * Definition of Interval:
 * public class Interval {
 *     public int start, end;
 *     public Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
class Solution {
    public int minMeetingRooms(List<Interval> intervals) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        intervals.sort((a, b) -> a.start - b.start);
        for (Interval interval : intervals) {
            if (!minHeap.isEmpty() && minHeap.peek() <= interval.start) {
                minHeap.poll();
            }
            minHeap.offer(interval.end);
        }
        return minHeap.size();
    }
}

6. Minimum Interval to Include Each Query

// 1. Brute Force
// 題目會給一堆 interval，以及要查詢的一堆數字，要在找到的多個 interval 內，找到最短的當結果
// 每個數字 for loop 所有 interval 找最佳解
//
// 假設有 n 個 interval，query k 個數字
// Time complexity: O(kn)
// Space complexity: O(k) for save result

// 2. sort + min heap
// 先將 interval 根據 start 進行排序
// queries 存成 query 和 index 的 int[]，然後根據 query 進行排序
// 在 for loop 每一個 queries 時，把符合 start < query 的 interval 放進 minHeap
// minHeap 是依據 length 來進行排序的，如果前幾個 query 的 end < query，則移除
// 即可從 min heap 拿到結果
//
// Time complexity: O(nlogn + klogk) -> O(nlogn)
// Space complexity: O(n + k)
//
// Dry run
// intervals = [[1,3],[2,3],[3,7],[6,6]], queries = [2,3,1,7,6,8]
// sortedIntervals: [[1,3],[2,3],[3,7],[6,6]]
// sortedQueries:[[1,2],[2,0],[3,1],[6,4],[7,3],[8,5]]
// [1,2] -> minHeap:[[1,3]], result[2]=3-1+1=3
// [2,0] -> minHeap:[[2,3], [1,3]], result[0]=3-2+1=2
// [3,1] -> minHeap:[[2,3], [1,3], [3,7]], result[1]=3-2+1=2
// [6,4] -> minHeap:[[6,6], [2,3], [1,3], [3,7]], result[4]=1
// [7,3] -> minHeap:[[3,7]], result[3]=7-3+1=5
// [8,5] -> minHeap:[], result[5]=-1
// result = [2,2,3,5,1,-1]
class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[][] sortedQueries = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            sortedQueries[i][0] = queries[i];
            sortedQueries[i][1] = i;
        }
        Arrays.sort(sortedQueries, (a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> (a[1] - a[0]) - (b[1] - b[0]));
        int j = 0;
        int[] result = new int[queries.length];
        for (int[] query : sortedQueries) {
            int q = query[0];
            int index = query[1];
            while (j < intervals.length && intervals[j][0] <= q) {
                minHeap.offer(intervals[j]);
                j++;
            }
            while (!minHeap.isEmpty() && minHeap.peek()[1] < q) {
                minHeap.poll();
            }
            result[index] = minHeap.isEmpty() ? -1 : minHeap.peek()[1] - minHeap.peek()[0] + 1;
        }
        return result;
    }
}