LeetCode#56 Merge Intervals

分析

原題連結

只要把 LeetCode#57 的 step1 改為排序即可，step2 照舊。

Source Code

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 * };
 */
class Solution {
public:
    static bool mycmp(const Interval &a, const Interval &b){
        return (a.start < b.start);
    }

    vector<Interval> merge(vector<Interval>& intervals) {
        if(intervals.size() == 0)
            return intervals;
        //step1
        sort(intervals.begin(), intervals.end(), mycmp);
        //step2
        vector<Interval> result;
        int start = intervals[0].start;
        int end = intervals[0].end;
        for(int i = 0; i < intervals.size(); ++i){
            if(end >= intervals[i].start){
                end = max(intervals[i].end, end);
            }else{
                result.push_back(Interval(start, end));
                start = intervals[i].start;
                end = intervals[i].end;
            }
        }            
        
        result.push_back(Interval(start, end));
        return result;
    }
};

應用

LeetCode#56,#57 除了顯示我司高大上之外，有沒有實際應用呢？有的，例如在工業通訊中，上位機的不同功能區塊(Alarm, DataLogger, Display...)從網路讀取控制器暫存器時，這些暫存器的位址往往會發生重疊，以三菱 PLC 為例，資料暫存器通常命名為 Dn，n 為 10 進位數值代表暫存器編號：

將這些重疊的位址合併，可以帶來以下好處：

• 節省頻寬
• 節省 request/response round-trip time

尤其對於串列通訊，9600bps 傳輸一個 byte 就要 1ms 左右(1/9600*10 = 1.04ms)，不必要的通訊可能浪費數十 ms 到上百 ms，這對控制器與上位機來說是非常大的損失(想想這些時間 CPU 可以做多少事)。

由此可見，某些公司考這些題目並非吃飽沒事幹故意整人，而是在他們的實際工作中曾經碰上類似的困難 :)