{"id":226782,"date":"2020-12-01T21:18:10","date_gmt":"2020-12-01T13:18:10","guid":{"rendered":"http:\/\/4563.org\/?p=226782"},"modified":"2020-12-01T21:18:10","modified_gmt":"2020-12-01T13:18:10","slug":"leetcode-lintcode-%e9%a2%98%e8%a7%a3-amazon-%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e6%95%b0%e9%a3%9e%e6%9c%ba","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=226782","title":{"rendered":"[leetcode\/lintcode \u9898\u89e3] Amazon \u9762\u8bd5\u9898\uff1a\u6570\u98de\u673a"},"content":{"rendered":"
\n
\n
\n

[leetcode\/lintcode \u9898\u89e3] Amazon \u9762\u8bd5\u9898\uff1a\u6570\u98de\u673a <\/h1>\n

<\/p>\n

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

\u7ed9\u51fa\u98de\u673a\u7684\u8d77\u98de\u548c\u964d\u843d\u65f6\u95f4\u7684\u5217\u8868\uff0c\u7528\u5e8f\u5217 interval \u8868\u793a. \u8bf7\u8ba1\u7b97\u51fa\u5929\u4e0a\u540c\u65f6\u6700\u591a\u6709\u591a\u5c11\u67b6\u98de\u673a\uff1f<\/p>\n

    \n
  • \u5982\u679c\u591a\u67b6\u98de\u673a\u964d\u843d\u548c\u8d77\u98de\u5728\u540c\u4e00\u65f6\u523b\uff0c\u6211\u4eec\u8ba4\u4e3a\u964d\u843d\u6709\u4f18\u5148\u6743\u3002<\/li>\n<\/ul>\n

    \u5728\u7ebf\u8bc4\u6d4b\u5730\u5740<\/p>\n

    \u6837\u4f8b 1:<\/h2>\n
    \u8f93\u5165: [(1, 10), (2, 3), (5, 8), (4, 7)] \u8f93\u51fa: 3 \u89e3\u91ca:  \u7b2c\u4e00\u67b6\u98de\u673a\u5728 1 \u65f6\u523b\u8d77\u98de, 10 \u65f6\u523b\u964d\u843d. \u7b2c\u4e8c\u67b6\u98de\u673a\u5728 2 \u65f6\u523b\u8d77\u98de, 3 \u65f6\u523b\u964d\u843d. \u7b2c\u4e09\u67b6\u98de\u673a\u5728 5 \u65f6\u523b\u8d77\u98de, 8 \u65f6\u523b\u964d\u843d. \u7b2c\u56db\u67b6\u98de\u673a\u5728 4 \u65f6\u523b\u8d77\u98de, 7 \u65f6\u523b\u964d\u843d. \u5728 5 \u65f6\u523b\u5230 6 \u65f6\u523b\u4e4b\u95f4, \u5929\u7a7a\u4e2d\u6709\u4e09\u67b6\u98de\u673a. <\/code><\/pre>\n
    \u6837\u4f8b 2:<\/h2>\n
    \u8f93\u5165: [(1, 2), (2, 3), (3, 4)] \u8f93\u51fa: 1 \u89e3\u91ca: \u964d\u843d\u4f18\u5148\u4e8e\u8d77\u98de. <\/code><\/pre>\n
    \u7b97\u6cd5\u4e00 \u524d\u7f00\u548c<\/h2>\n
    \u5728\u5f00\u59cb\u65f6\u95f4\u4f4d\u7f6e+1 \u67b6\u98de\u673a\uff0c\u5728\u7ed3\u675f\u65f6\u95f4-1 \u67b6\u98de\u673a\uff0c\u6c42\u4e00\u904d\u524d\u7f00\u548c\uff0c\u5c31\u662f\u5bf9\u5e94\u65f6\u95f4\u98de\u673a\u7684\u6570\u91cf, \u524d\u7f00\u548c\u7b97\u6cd5\u6d89\u53ca\u5230\u4e86\u5bf9\u65f6\u95f4\u79bb\u6563\u5316\uff0c\u6240\u4ee5\u8fd9\u91cc\u66f4\u63a8\u8350\u626b\u63cf\u7ebf<\/p>\n
    \u7b97\u6cd5\u4e8c \u626b\u63cf\u7ebf<\/h2>\n
    \u626b\u63cf\u7ebf\uff0c\u628a\u98de\u673a\u6309\u5f00\u59cb\u65f6\u95f4\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\uff0c\u5982\u679c\u5f00\u59cb\u65f6\u95f4\u76f8\u540c\uff0c\u7ed3\u675f\u65f6\u95f4\u5c0f\u7684\u5728\u524d\uff0c \u626b\u63cf\u4e00\u904d\uff0c\u5f53\u626b\u63cf\u5230\u5f00\u59cb\u65f6\u95f4\uff0c\u5c31\u4f1a\u591a\u4e00\u67b6\u98de\u673a,\u98de\u673a\u6570+1\uff0c\u5f53\u626b\u63cf\u5230\u7ed3\u675f\u65f6\u95f4\u5c31\u5c11\u4e00\u67b6\u98de\u673a\uff0c\u98de\u673a\u6570-1 \u7b54\u6848\u53d6\u626b\u63cf\u8fc7\u7a0b\u4e2d\u7684\u6700\u5927\u98de\u673a\u6570<\/p>\n
    \u590d\u6742\u5ea6\u5206\u6790<\/h2>\n
    \u65f6\u95f4\u590d\u6742\u5ea6<\/h3>\n
    \u7b97\u6cd5\u4e00 \u524d\u7f00\u548c \u524d\u7f00\u548c O(Time)\uff0cTime \u8868\u793a\u6700\u5927\u65f6\u95f4<\/p>\n
    \u7b97\u6cd5\u4e8c \u626b\u63cf\u7ebf \u626b\u63cf\u7ebf O(NlogN)\uff0cN \u662f\u98de\u673a\u6570\u91cf<\/p>\n
    \u7a7a\u95f4\u590d\u6742\u5ea6<\/h3>\n
    \u7b97\u6cd5\u4e00 \u524d\u7f00\u548c \u524d\u7f00\u548c O(Time)\uff0cTime \u8868\u793a\u6700\u5927\u65f6\u95f4<\/p>\n
    \u7b97\u6cd5\u4e8c \u626b\u63cf\u7ebf \u626b\u63cf\u7ebf O(N)\uff0cN \u662f\u98de\u673a\u6570\u91cf<\/p>\n
    public class Solution {     \/**      * @param airplanes: an array of meeting time airplanes      * @return: the minimum number of conference rooms required      *\/     static class Node {         public int time;         public int cost;         public Node() {         }         \/\/ \u65f6\u95f4\uff0c\u5f00\u59cb\u65f6\u95f4 cost \u4e3a 1\uff0c\u7ed3\u675f\u65f6\u95f4 cost \u4e3a-1         public Node(int time, int cost) {             this.time = time;             this.cost = cost;         }     }     \/\/\u5148\u6309\u7167\u65f6\u95f4\u5347\u5e8f\uff0c\u518d\u6309\u7167 cost \u5347\u5e8f\u6392\u5e8f     static Comparator cNode = new Comparator() {         public int compare(Node o1, Node o2) {             if(o1.time != o2.time) {                 return o1.time - o2.time;             }             return o1.cost - o2.cost;         }     };      public int countOfAirplanes(List airplanes) {         \/\/\u626b\u63cf\u7ebf\u6570\u7ec4         Listroom = new ArrayList();         for(int i = 0; i < airplanes.size(); i++) {             room.add(new Node(airplanes.get(i).start, 1));             room.add(new Node(airplanes.get(i).end, -1));         }         \/\/\u6392\u5e8f         Collections.sort(room, cNode);         int ans = 0;         int tmp = 0;         for(int i = 0; i < room.size(); i++) {             tmp += room.get(i).cost;             ans = Math.max(ans, tmp);         }         return ans;     } } <\/code><\/pre>\n
    \u66f4\u591a\u9898\u89e3\u53c2\u8003<\/p>\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\/226782"}],"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=226782"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/226782\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=226782"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=226782"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=226782"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}