changed 2 years ago  
Published Linked with GitHub

Leetcode刷題學習筆記 – Line Sweep

Intrudoction

Line Sweep顧名思義，就是針對x或是y軸依序掃描過去。
例如下圖，針對不同的interval，對x軸掃描。從最左邊掃到最右邊。

Line Sweep

因為，需要從最小掃到最大。所以interval必須要拆成起點和終點，分別給不同的flag，放進一個vector之後遞增排序。

Code Snippet

給你一個vector<vector<int>> intervals來代表區間，vector<int> queries來查詢在x = queries[i] 的時候有多少個重複interval，使用interval和queries來建立line sweep的準備資料。

enum state{start, end};
vector<vector<int>> intervals;
vector<vector<int>> db;

for(auto& itv : intervals) {
    db.push_back({itv[0], start});
    db.push_back({itv[1], end, itv[0]});
}

for(int i = 0; i < queries.size(); ++i)
    db.push_back({queries[i], query, i});
    
sort(db.begin(), db.end());

建立好準備資料，就可以根據題目依序拿出item來做處理。

vector<int> ans(queries.size());
unordered_multiset<int> ms;
for(auto& item : db) {
    switch(item[1]) {
        case start: 
            ms.insert(item[0]); 
            break;
        case query: 
            ans[item[2]] = ms.empty() ? -1 : ms.size(); 
            break;
        case end : 
            ms.erase(ms.find(item[2])); 
            break;
    }
}
    
return ans;

Problem

1851. Minimum Interval to Include Each Query

給定vector<vector<int>> interval，找出每個query的x值，長度最小的interval。如果沒有則回傳-1。

  1. 因為是interval可以使用line sweep。
  2. 將query當成第二個，因為這邊的interval定義是前後都有包含。所以先查詢之後再刪除。
  3. 第三個欄位放每個interval的size。
  4. 因為要找出最小的interval所以使用multiset來對遇到的interval進行排序。
class Solution {
    enum state {start, query, end};
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        vector<vector<int>> db;
        for(auto& itv : intervals) {
            int sz = itv[1] - itv[0] + 1;
            db.push_back({itv[0], start, sz});
            db.push_back({itv[1], end, sz});
        }
        for(int i = 0; i < queries.size(); ++i) {
            db.push_back({queries[i], query, i});
        }
        sort(db.begin(), db.end());

        vector<int> ans(queries.size());
        multiset<int> ms;
        for(auto& item : db) {
            if(item[1] == start) ms.insert(item[2]);
            else if(item[1] == query) {
                if(ms.empty()) ans[item[2]] = -1;
                else ans[item[2]] = *ms.begin();
            } else
                ms.erase(ms.find(item[2]));
        }

        return ans;
    }
};
  • 2023/07/18 重做一次還是沒想到使用line sweep。
  • line sweep可以想成是走訪整個時間軸。或是依序走訪x軸。
  • 先建立掃描的順序。
    1. interval的起始點 (把length放進multiset)
    2. query點 (從multiset拿出最小值)
    3. interval的終點 (把length從multiset移除)
  • 依序走訪得出答案。

218. The Skyline Problem

找出重疊矩形的邊緣。如下圖所示。

example

一開始對這種題目完全沒想法。如果是面試應該當場傻掉。
不過後來看答案之後，原來是使用Line Sweep。另外當沒有想法的時候，如果不擠點東西出來，在面試場合應該也不好看。

  1. 先觀察給的example的答案。
  2. 解答都是出現在高度有變化的地方 ==> 判斷高度改變就儲存答案。
  3. 判斷的地方都是每個方塊的x起點和x終點。 ==> line sweep
  4. 重點 因為我們必須排列x從小到大，如果x一樣則y從大到小。 ==> 所以start-point {b[0], -b[2]}, end-point {b[1], b[2]}，因為當x一樣，最大的y就會排在前面。

為什麼要這樣排列?
當矩形重疊時，{1, 2, 1}, {1, 2, 2}, {1, 2, 3}
存入height之後

這邊也是個重點，把成對的vector排列成像竹筍的樣子。

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> height; // x, y
        multiset<int> hlist;
        for(auto& b : buildings) {
            height.emplace_back(b[0], -b[2]); // start
            height.emplace_back(b[1], b[2]); // end
        }
        sort(begin(height), end(height));
        hlist.insert(0); // 從高度0開始
        int cur{0}, prev{0};
        vector<vector<int>> ans;
        for(auto& [x, y] : height) {
            if(y < 0) hlist.insert(-y); // 矩形起點，儲存高度。
            else hlist.erase(hlist.find(y)); // 矩形終點，所以把這個矩形的高度刪掉
            cur = *hlist.rbegin(); // 取最高的高度
            if(cur != prev) { // 高度改變
                ans.push_back({x, cur});
                prev = cur;
            }
        }
        return ans;
    }
};
tags: leetcode 刷題
Select a repo