{"id":7395,"date":"2026-07-21T21:20:36","date_gmt":"2026-07-21T13:20:36","guid":{"rendered":"https:\/\/i007.cc\/wordpress\/?p=7395"},"modified":"2026-07-21T21:20:36","modified_gmt":"2026-07-21T13:20:36","slug":"%e5%90%88%e5%b9%b6%e5%8c%ba%e9%97%b4%ef%bc%88merge-intervals%ef%bc%89","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/7395","title":{"rendered":"\u5408\u5e76\u533a\u95f4\uff08Merge Intervals\uff09"},"content":{"rendered":"<p class=\"font-claude-response-body break-words whitespace-normal\" dir=\"auto\">\u529b\u6263\u7b2c 56 \u9898\u3002\u7ed9\u4e00\u7ec4\u533a\u95f4\uff0c\u628a\u6240\u6709\u91cd\u53e0\u7684\u533a\u95f4\u5408\u5e76\uff0c\u8fd4\u56de\u5408\u5e76\u540e\u7684\u7ed3\u679c\u3002<\/p>\n<hr class=\"border-border-200 border-t-0.5 my-3 mx-1.5\" \/>\n<h4 class=\"text-text-100 mt-2 -mb-1 text-base font-bold\" dir=\"auto\">\u6838\u5fc3\u601d\u8def\uff1a\u6392\u5e8f + \u7ebf\u6027\u626b\u63cf<\/h4>\n<p class=\"font-claude-response-body break-words whitespace-normal\" dir=\"auto\">\u66b4\u529b\u505a\u6cd5\u662f\u4e24\u4e24\u6bd4\u8f83\uff0cO(n\u00b2)\u3002\u6700\u4f18\u505a\u6cd5\u662f\u5148\u6392\u5e8f\uff0c\u6392\u5e8f\u540e<strong>\u91cd\u53e0\u7684\u533a\u95f4\u4e00\u5b9a\u76f8\u90bb<\/strong>\uff0c\u5c31\u53ef\u4ee5\u4e00\u6b21\u7ebf\u6027\u626b\u63cf\u641e\u5b9a\u3002<\/p>\n<hr class=\"border-border-200 border-t-0.5 my-3 mx-1.5\" \/>\n<h4 class=\"text-text-100 mt-2 -mb-1 text-base font-bold\" dir=\"auto\">\u6700\u4f18\u89e3\u6cd5<\/h4>\n<div class=\"relative group\/copy bg-bg-000\/50 border-0.5 border-border-400 rounded-lg focus:outline-none focus-visible:ring-2 focus-visible:ring-accent-100\" tabindex=\"0\" role=\"group\" aria-label=\"cpp code\">\n<div class=\"sticky opacity-0 group-hover\/copy:opacity-100 group-focus-within\/copy:opacity-100 top-2 py-2 h-12 w-0 float-right\">\n<div class=\"absolute right-0 h-8 px-2 items-center inline-flex z-10\"><\/div>\n<\/div>\n<div class=\"text-text-500 font-small p-3.5 pb-0\">cpp<\/div>\n<div class=\"overflow-x-auto\">\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">vector&lt;vector&lt;int&gt;&gt; merge(vector&lt;vector&lt;int&gt;&gt;&amp; intervals) {\r\n    \/\/ 1. \u6309\u5de6\u7aef\u70b9\u6392\u5e8f\r\n    sort(intervals.begin(), intervals.end());\r\n\r\n    vector&lt;vector&lt;int&gt;&gt; ans;\r\n\r\n    for (auto&amp; cur : intervals) {\r\n        \/\/ 2. \u5982\u679c\u7ed3\u679c\u96c6\u4e3a\u7a7a\uff0c\u6216\u5f53\u524d\u533a\u95f4\u4e0e\u6700\u540e\u4e00\u4e2a\u4e0d\u91cd\u53e0\uff0c\u76f4\u63a5\u52a0\u5165\r\n        if (ans.empty() || cur[0] &gt; ans.back()[1]) {\r\n            ans.push_back(cur);\r\n        }\r\n        \/\/ 3. \u5426\u5219\u6709\u91cd\u53e0\uff0c\u5408\u5e76\uff1a\u53f3\u7aef\u70b9\u53d6\u6700\u5927\u503c\r\n        else {\r\n            ans.back()[1] = max(ans.back()[1], cur[1]);\r\n        }\r\n    }\r\n\r\n    return ans;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n<\/div>\n<hr class=\"border-border-200 border-t-0.5 my-3 mx-1.5\" \/>\n<h4 class=\"text-text-100 mt-2 -mb-1 text-base font-bold\" dir=\"auto\">\u4e3a\u4ec0\u4e48\u6392\u5e8f\u540e\u53ea\u9700\u770b&#8221;\u6700\u540e\u4e00\u4e2a&#8221;\uff1f<\/h4>\n<p class=\"font-claude-response-body break-words whitespace-normal\" dir=\"auto\">\u6392\u5e8f\u540e\uff0c\u533a\u95f4\u6309\u5de6\u7aef\u70b9\u4ece\u5c0f\u5230\u5927\u6392\u5217\u3002\u5bf9\u4e8e\u5f53\u524d\u533a\u95f4 <code class=\"bg-text-200\/5 border border-0.5 border-border-300 text-danger-000 whitespace-pre-wrap rounded-[0.4rem] px-1 py-px text-[0.9rem]\">cur<\/code>\uff0c\u5b83\u53ea\u53ef\u80fd\u4e0e<strong>\u7d27\u90bb\u7684\u524d\u4e00\u4e2a<\/strong>\u53d1\u751f\u91cd\u53e0\uff0c\u4e0d\u53ef\u80fd\u8de8\u8d8a\u53bb\u548c\u66f4\u65e9\u7684\u533a\u95f4\u91cd\u53e0\u2014\u2014\u56e0\u4e3a\u4e2d\u95f4\u7684\u533a\u95f4\u5de6\u7aef\u70b9\u66f4\u5c0f\uff0c\u5982\u679c\u5b83\u4eec\u80fd\u5408\u5e76\u65e9\u5c31\u5408\u5e76\u4e86\u3002<\/p>\n<p class=\"font-claude-response-body break-words whitespace-normal\" dir=\"auto\">\u6240\u4ee5\u6bcf\u6b21\u53ea\u9700\u8981\u770b <code class=\"bg-text-200\/5 border border-0.5 border-border-300 text-danger-000 whitespace-pre-wrap rounded-[0.4rem] px-1 py-px text-[0.9rem]\">ans.back()<\/code> \u5c31\u591f\u4e86\uff0c\u4e0d\u9700\u8981\u56de\u5934\u770b\u3002<\/p>\n<hr class=\"border-border-200 border-t-0.5 my-3 mx-1.5\" \/>\n<h4 class=\"text-text-100 mt-2 -mb-1 text-base font-bold\" dir=\"auto\">\u91cd\u53e0\u5224\u65ad\u7684\u5173\u952e\uff1a\u53ea\u770b\u53f3\u7aef\u70b9<\/h4>\n<div class=\"relative group\/copy bg-bg-000\/50 border-0.5 border-border-400 rounded-lg focus:outline-none focus-visible:ring-2 focus-visible:ring-accent-100\" tabindex=\"0\" role=\"group\" aria-label=\"Code\">\n<div class=\"sticky opacity-0 group-hover\/copy:opacity-100 group-focus-within\/copy:opacity-100 top-2 py-2 h-12 w-0 float-right\">\n<div class=\"absolute right-0 h-8 px-2 items-center inline-flex z-10\"><\/div>\n<\/div>\n<div class=\"overflow-x-auto\">\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">\u5df2\u6709\u533a\u95f4:  [----]\r\n\u5f53\u524d\u533a\u95f4:      [----]   \u2192 \u91cd\u53e0\uff0c\u5408\u5e76\r\n\u5f53\u524d\u533a\u95f4:          [--] \u2192 \u4e0d\u91cd\u53e0\uff0c\u76f4\u63a5\u52a0\u5165<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n<\/div>\n<p class=\"font-claude-response-body break-words whitespace-normal\" dir=\"auto\">\u91cd\u53e0\u6761\u4ef6\uff1a<code class=\"bg-text-200\/5 border border-0.5 border-border-300 text-danger-000 whitespace-pre-wrap rounded-[0.4rem] px-1 py-px text-[0.9rem]\">cur[0] &lt;= ans.back()[1]<\/code>\uff08\u5de6\u7aef\u70b9\u6392\u5e8f\u540e\uff0c\u5de6\u7aef\u70b9\u5927\u5c0f\u4e0d\u7528\u62c5\u5fc3\uff0c\u53ea\u9700\u5224\u65ad\u53f3\u7aef\u70b9\uff09<\/p>\n<p class=\"font-claude-response-body break-words whitespace-normal\" dir=\"auto\">\u5408\u5e76\u65f6\u53f3\u7aef\u70b9\u53d6 <code class=\"bg-text-200\/5 border border-0.5 border-border-300 text-danger-000 whitespace-pre-wrap rounded-[0.4rem] px-1 py-px text-[0.9rem]\">max<\/code>\uff0c\u662f\u4e3a\u4e86\u5904\u7406\u88ab\u5b8c\u5168\u5305\u542b\u7684\u60c5\u51b5\uff1a<\/p>\n<div class=\"relative group\/copy bg-bg-000\/50 border-0.5 border-border-400 rounded-lg focus:outline-none focus-visible:ring-2 focus-visible:ring-accent-100\" tabindex=\"0\" role=\"group\" aria-label=\"Code\">\n<div class=\"sticky opacity-0 group-hover\/copy:opacity-100 group-focus-within\/copy:opacity-100 top-2 py-2 h-12 w-0 float-right\">\n<div class=\"absolute right-0 h-8 px-2 items-center inline-flex z-10\"><\/div>\n<\/div>\n<div class=\"overflow-x-auto\">\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">\u5df2\u6709\u533a\u95f4:  [----------]\r\n\u5f53\u524d\u533a\u95f4:    [----]      \u2192 cur[1] &lt; ans.back()[1]\uff0c\u53f3\u7aef\u70b9\u4e0d\u80fd\u7f29\u5c0f<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n<\/div>\n<hr class=\"border-border-200 border-t-0.5 my-3 mx-1.5\" \/>\n<h4 class=\"text-text-100 mt-2 -mb-1 text-base font-bold\" dir=\"auto\">\u8d70\u4e00\u904d\u4f8b\u5b50<\/h4>\n<div class=\"relative group\/copy bg-bg-000\/50 border-0.5 border-border-400 rounded-lg focus:outline-none focus-visible:ring-2 focus-visible:ring-accent-100\" tabindex=\"0\" role=\"group\" aria-label=\"Code\">\n<div class=\"sticky opacity-0 group-hover\/copy:opacity-100 group-focus-within\/copy:opacity-100 top-2 py-2 h-12 w-0 float-right\">\n<div class=\"absolute right-0 h-8 px-2 items-center inline-flex z-10\"><\/div>\n<\/div>\n<div class=\"overflow-x-auto\">\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">\u8f93\u5165: [[1,3],[2,6],[8,10],[15,18]]\r\n\u6392\u5e8f\u540e\uff08\u5df2\u6709\u5e8f\uff09: [[1,3],[2,6],[8,10],[15,18]]\r\n\r\n\u5904\u7406 [1,3]: ans \u4e3a\u7a7a\uff0c\u52a0\u5165 \u2192 ans = [[1,3]]\r\n\u5904\u7406 [2,6]: 2 &lt;= 3\uff0c\u91cd\u53e0\uff0c\u53f3\u7aef\u70b9\u53d6 max(3,6)=6 \u2192 ans = [[1,6]]\r\n\u5904\u7406 [8,10]: 8 &gt; 6\uff0c\u4e0d\u91cd\u53e0\uff0c\u52a0\u5165 \u2192 ans = [[1,6],[8,10]]\r\n\u5904\u7406 [15,18]: 15 &gt; 10\uff0c\u4e0d\u91cd\u53e0\uff0c\u52a0\u5165 \u2192 ans = [[1,6],[8,10],[15,18]]<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n<\/div>\n<hr class=\"border-border-200 border-t-0.5 my-3 mx-1.5\" \/>\n<h4 class=\"text-text-100 mt-2 -mb-1 text-base font-bold\" dir=\"auto\">\u590d\u6742\u5ea6<\/h4>\n<div class=\"overflow-x-auto w-full px-2 mb-6\" dir=\"auto\">\n<table class=\"min-w-full border-collapse text-sm leading-[1.7] whitespace-normal\">\n<thead class=\"text-left\">\n<tr>\n<th class=\"text-text-100 border-b-0.5 border-[hsl(var(--border-300)\/0.6)] py-2 pr-4 align-top font-bold\" scope=\"col\">\u7ef4\u5ea6<\/th>\n<th class=\"text-text-100 border-b-0.5 border-[hsl(var(--border-300)\/0.6)] py-2 pr-4 align-top font-bold\" scope=\"col\">\u590d\u6742\u5ea6<\/th>\n<th class=\"text-text-100 border-b-0.5 border-[hsl(var(--border-300)\/0.6)] py-2 pr-4 align-top font-bold\" scope=\"col\">\u8bf4\u660e<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td class=\"border-b-0.5 border-[hsl(var(--border-300)\/0.3)] py-2 pr-4 align-top\">\u65f6\u95f4<\/td>\n<td class=\"border-b-0.5 border-[hsl(var(--border-300)\/0.3)] py-2 pr-4 align-top\">O(n log n)<\/td>\n<td class=\"border-b-0.5 border-[hsl(var(--border-300)\/0.3)] py-2 pr-4 align-top\">\u74f6\u9888\u5728\u6392\u5e8f\uff0c\u626b\u63cf\u662f O(n)<\/td>\n<\/tr>\n<tr>\n<td class=\"border-b-0.5 border-[hsl(var(--border-300)\/0.3)] py-2 pr-4 align-top\">\u7a7a\u95f4<\/td>\n<td class=\"border-b-0.5 border-[hsl(var(--border-300)\/0.3)] py-2 pr-4 align-top\">O(1)<\/td>\n<td class=\"border-b-0.5 border-[hsl(var(--border-300)\/0.3)] py-2 pr-4 align-top\">\u4e0d\u7b97\u8f93\u51fa\u7684\u8bdd\uff0c\u539f\u5730\u64cd\u4f5c<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p class=\"font-claude-response-body break-words whitespace-normal\" dir=\"auto\">\u8fd9\u9053\u9898<strong>\u4e0d\u80fd\u505a\u5230 O(n)<\/strong>\uff0c\u56e0\u4e3a\u5fc5\u987b\u6392\u5e8f\u2014\u2014\u6392\u5e8f\u7684 O(n log n) \u4e0b\u754c\u65e0\u6cd5\u7a81\u7834\uff08\u9664\u975e\u8f93\u5165\u5df2\u6709\u5e8f\uff09\u3002<\/p>\n<hr class=\"border-border-200 border-t-0.5 my-3 mx-1.5\" \/>\n<h4 class=\"text-text-100 mt-2 -mb-1 text-base font-bold\" dir=\"auto\">\u4e00\u4e2a\u53d8\u4f53\u8981\u6ce8\u610f<\/h4>\n<p class=\"font-claude-response-body break-words whitespace-normal\" dir=\"auto\"><strong>\u63d2\u5165\u533a\u95f4\uff08\u529b\u6263 57 \u9898\uff09<\/strong>\uff1a\u7ed9\u4e00\u4e2a\u5df2\u6392\u5e8f\u4e14\u4e0d\u91cd\u53e0\u7684\u533a\u95f4\u5217\u8868\uff0c\u63d2\u5165\u4e00\u4e2a\u65b0\u533a\u95f4\uff0c\u8fd4\u56de\u5408\u5e76\u540e\u7ed3\u679c\u3002\u601d\u8def\u662f\u628a\u65b0\u533a\u95f4\u76f4\u63a5\u63d2\u5165\u540e\u8c03\u7528 merge\uff0c\u6216\u8005\u66f4\u4f18\u96c5\u5730\u5206\u4e09\u6bb5\u5904\u7406\uff08\u65b0\u533a\u95f4\u5de6\u8fb9\u4e0d\u91cd\u53e0\u7684\u3001\u91cd\u53e0\u9700\u5408\u5e76\u7684\u3001\u53f3\u8fb9\u4e0d\u91cd\u53e0\u7684\uff09\uff0cO(n) \u89e3\u51b3\u3002\u638c\u63e1\u4e86\u672c\u9898\u518d\u505a 57 \u9898\u5c31\u662f\u6c34\u5230\u6e20\u6210\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u529b\u6263\u7b2c 56 \u9898\u3002\u7ed9\u4e00\u7ec4\u533a\u95f4\uff0c\u628a\u6240\u6709\u91cd\u53e0<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[24],"tags":[],"class_list":["post-7395","post","type-post","status-publish","format-standard","hentry","category-value_docs"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7395","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=7395"}],"version-history":[{"count":1,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7395\/revisions"}],"predecessor-version":[{"id":7396,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7395\/revisions\/7396"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=7395"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=7395"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=7395"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}