2017年1月5日 星期四

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 可以做多少事)。

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

沒有留言:

張貼留言