MaxCoverage

暴力解

• 暴力解
• 有加入 early finishing 減少不必要的計算

func maxCoverage(nums: [Int], subsets: [[Int]]) -> [[Int]] {
    var maxMatch: Int = 0
    var results: [[Int]] = [[]]

    // O(n), 需要全部走訪
    for (index, subset) in subsets.enumerated() {
        // 每次換主數組就重置 numsSet
        var numsSet = Set(nums)

        // O(m), m subsets 所包含的 Int 總數
        // Early finishing, 如果主數組已經沒在 subset 裡面就不繼續處理了
        if numsSet.isSuperset(of: subset) {
            var result: [[Int]] = [subset]
            var match = subset.count

            // O(m)
            numsSet = numsSet.subtracting(subset)

            // O(n), 最壞情形需要全部走訪
            for pointer in (index + 1)..<subsets.count {
                let current = subsets[pointer]
                // O(m), early finishing 
                // 如果沒交集才開始處理
                if !subset.contains(where: current.contains)
                    // O(m), early finishing 
                    // 如果和 `nums` 有交集才開始處理
                    && numsSet.isSuperset(of: current) {
                    result.append(Array(current))
                    match += current.count
                    // O(m)
                    numsSet = numsSet.subtracting(current)
                }
            }
            
            // 當前結果優於暫存結果的話則替換
            if match > maxMatch {
                maxMatch = match
                results = result
            }
        }
    }
    
    return results
}

時間複雜度為

O(n^2 + 4m) => O(n^2 + m)

執行

let nums = [0, 1, 2, 3, 4, 5]
let subsets = [[1, 3], [2, 3, 4, 5], [1, 4, 5], [2, 3]]

let start = Date()
let result = maxCoverage(nums: nums, subsets: subsets)
let end = Date()

print(end.timeIntervalSinceReferenceDate - start.timeIntervalSinceReferenceDate)
print(result)

0.018952012062072754
[[1, 4, 5], [2, 3]]

其他嘗試

先排序 subsets

在最前面先排序（理論上時間複雜度會增加 O(nlogn)）

let subsets = subsets.sorted { $0.count > $1.count }

但是執行時間沒有太大的改善