{"id":424025,"date":"2021-04-04T01:32:03","date_gmt":"2021-04-03T17:32:03","guid":{"rendered":"http:\/\/4563.org\/?p=424025"},"modified":"2021-04-04T01:32:03","modified_gmt":"2021-04-03T17:32:03","slug":"leetcode-lintcode-%e9%a2%98%e8%a7%a3-facebook-%e8%84%b8%e4%b9%a6%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e6%8f%92%e5%85%a5%e5%8c%ba%e9%97%b4","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=424025","title":{"rendered":"[leetcode\/lintcode \u9898\u89e3] Facebook \u8138\u4e66\u9762\u8bd5\u9898\uff1a\u63d2\u5165\u533a\u95f4"},"content":{"rendered":"
\n
\n
\n

[leetcode\/lintcode \u9898\u89e3] Facebook \u8138\u4e66\u9762\u8bd5\u9898\uff1a\u63d2\u5165\u533a\u95f4 <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span> <\/i> 0<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u9898\u76ee\u63cf\u8ff0\u53ef\u4ee5\u770b\u8fd9\u91cc<\/strong> <\/p>\n

\u7b97\u6cd5\uff1a\u6a21\u62df<\/h2>\n

\u53ea\u8981\u4f9d\u6b21\u904d\u5386\uff0c\u5224\u65ad\u5f53\u524d\u5143\u7d20\u4e0e\u8981\u63d2\u5165\u5143\u7d20\u7684\u5173\u7cfb\u3002<\/p>\n

    \n
  • \n

    \u5982\u5f53\u524d\u5143\u7d20\u7684\u53f3\u7aef\u70b9\u5c0f\u4e8e\u63d2\u5165\u5143\u7d20\u7684\u5de6\u7aef\u70b9\uff0c\u5219\u8bf4\u660e\u5f53\u524d\u5143\u7d20\u4e0e\u63d2\u5165\u5143\u7d20\u65e0\u4ea4\u5e76\u3002<\/p>\n<\/li>\n

  • \n

    \u5982\u5f53\u524d\u5143\u7d20\u7684\u5de6\u7aef\u70b9\u5927\u4e8e\u63d2\u5165\u5143\u7d20\u7684\u53f3\u7aef\u70b9\uff0c\u4e5f\u8bf4\u660e\u5f53\u524d\u5143\u7d20\u4e0e\u63d2\u5165\u5143\u7d20\u65e0\u4ea4\u5e76\u3002<\/p>\n<\/li>\n<\/ul>\n

    \u4f9d\u6b21\u904d\u5386\uff0c\u5224\u65ad\u5f53\u524d\u5143\u7d20\u4e0e\u8981\u63d2\u5165\u5143\u7d20\u7684\u5173\u7cfb\uff0c\u627e\u5230\u63d2\u5165\u70b9\uff0c\u63d2\u5165\u8fd9\u4e2a\u65b0\u533a\u95f4<\/p>\n

      \n
    • \u82e5\u662f\u76f8\u4ea4\u7684\uff0c\u90a3\u4e48\u5c31\u505c\u6b62\u6bd4\u8f83\uff0c\u628a\u8981\u63d2\u5165\u5143\u7d20\u548c\u5f53\u524d\u5143\u7d20\u5408\u5e76\u6210\u65b0\u533a\u95f4 \u56e0\u4e3a\u5408\u5e76\u540e\u7684\u65b0\u533a\u95f4\u4e5f\u8bb8\u548c\u53f3\u8fb9\u7684\u5143\u7d20\u6709\u4ea4\u96c6\uff0c\u4f1a\u5f15\u8d77\u8fde\u9501\u53cd\u5e94\uff0c\u6240\u4ee5\u4e00\u76f4\u548c\u53f3\u8fb9\u7684\u5143\u7d20\u5408\u5e76\uff0c\u76f4\u5230\u65e0\u6cd5\u5408\u5e76\u4e3a\u6b62<\/li>\n<\/ul>\n

      \u590d\u6742\u5ea6\u5206\u6790<\/h3>\n
        \n
      • \u65f6\u95f4\u590d\u6742\u5ea6 O(n)\n
          \n
        • n \u4e3a\u6570\u7ec4\u7684\u5927\u5c0f<\/li>\n<\/ul>\n<\/li>\n
        • \u7a7a\u95f4\u590d\u6742\u5ea6 O(n)\n
            \n
          • n \u4e3a\u6570\u7ec4\u7684\u5927\u5c0f<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n

            \u4ee3\u7801<\/h3>\n
            \/**  * Definition of Interval:  * public classs Interval {  *     int start, end;  *     Interval(int start, int end) {  *         this.start = start;  *         this.end = end;  *     }  *\/    public class Solution {     \/*      * @param intervals: Sorted interval list.      * @param newInterval: new interval.      * @return: A new interval list.      *\/     public List<Interval> insert(List<Interval> intervals, Interval newInterval) {         List<Interval> newIntervals = new ArrayList<Interval>();         if(intervals.size() == 0){             newIntervals.add(newInterval);         }         for (int i = 0; i < intervals.size(); i++) {             \/\/ \u5982\u679c\u65b0\u533a\u95f4\u7684\u7ed3\u675f\u503c\u5c0f\u4e8e\u533a\u95f4\u5f00\u59cb\u503c\uff0c\u63d2\u5728\u8fd9\u91cc\uff0c\u540e\u9762\u7eed\u4e0a             if (newInterval.end < intervals.get(i).start) {                 newIntervals.add(newInterval);                 for (int j = i; j < intervals.size(); j++) {                     newIntervals.add(intervals.get(j));                 }                 break;             }             \/\/ \u5982\u679c\u65b0\u533a\u95f4\u7684\u5f00\u59cb\u503c\u5927\u4e8e\u533a\u95f4\u7ed3\u675f\u503c\uff0c\u628a\u5f53\u524d\u533a\u95f4\u52a0\u8fdb\u53bb             else if (newInterval.start > intervals.get(i).end) {                 newIntervals.add(intervals.get(i));             }             \/\/ \u51fa\u73b0\u4ea4\u53c9\uff0c\u9700\u8981\u5408\u5e76             else {                 newInterval.start = Math.min(newInterval.start, intervals.get(i).start);                 newInterval.end = Math.max(newInterval.end, intervals.get(i).end);             }             \/\/ \u6700\u540e\u53ea\u5269\u4e00\u4e2a\u6570\u636e\u4e86\uff0c\u6dfb\u52a0\u8fdb\u53bb             if(i == intervals.size() - 1){                 newIntervals.add(newInterval);             }         }         return newIntervals;     } } <\/code><\/pre>\n<\/p><\/div>\n
             \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (0<\/span>)        <\/div>\n
             <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
              \n
            • \n","protected":false},"excerpt":{"rendered":"
              [leetcode\/lintcod…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/424025"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=424025"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/424025\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=424025"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=424025"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=424025"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}