C++ 合并区间算法实现：使用 Bitset 优化

{ "title": "C++ 合并区间算法实现：使用 Bitset 优化", "description": "本文介绍了一种使用 Bitset 优化 C++ 合并区间算法的实现方法。该方法利用 Bitset 来记录区间的覆盖情况，并通过遍历 Bitset 来找到合并后的区间。", "keywords": "合并区间, 算法, C++, Bitset, 优化", "content": ""class Solution {\npublic:\n\tbitset<20005> s;bool first;\n\tint a=-1,b=-1,lb=INT_MAX,ub=INT_MIN;\n\tvector<vector> merge(vector<vector>& intervals){\n\t s.reset();\n\t vector<vector> ans;\n\t for(int i=0;i<intervals.size();i++){\n\t first=1;\n\t lb=min(lb,(intervals[i][0]<<1)+1);\n\t ub=max(ub,(intervals[i][1]<<1)+1);\n\t for(int j=(intervals[i][0]<<1)+1;j<=(intervals[i][1]<<1)+1;j+=2){\n\t s[j]=1;\n\t if(first) first=0;\n\t else s[j-1]=1;\n\t }\n\t }\n\t for(int i=lb;i<ub+3;i+=2){\n\t if(s[i]&&s[i+1]){\n\t if(!~a) a=b=i;\n\t else b+=2;\n\t }else if(s[i]&&!s[i-1]) ans.emplace_back(vector({i-1>>1,i-1>>1}));\n\t else{\n\t if(~a&&~b) ans.emplace_back(vector({a-1>>1,b+1>>1}));\n\t a=b=-1;\n\t }\n\t }\n\t return ans;\n\t}\n};//分析一下此代码内容：此代码实现了合并区间的功能。首先，定义了一个大小为20005的bitset数组s，用于记录区间的覆盖情况。同时定义了变量a、b、lb和ub，分别记录当前合并区间的起始点、结束点、最小起始点和最大结束点。\n\n在merge函数中，先将bitset数组s全部置为0，然后遍历intervals数组。对于每个区间intervals[i]，将lb更新为min(lb, (intervals[i][0] << 1) + 1)，ub更新为max(ub, (intervals[i][1] << 1) + 1)。然后，对于区间intervals[i]中的每个点，将其对应的bitset数组s中的位置置为1，并且将前一个位置也置为1（表示该点与前一个点之间的区间被覆盖）。\n\n接下来，从lb开始遍历bitset数组s，判断当前位置和下一个位置的值。如果两个位置都为1，则表示当前区间被覆盖，需要更新合并区间的起始点和结束点；如果当前位置为1且下一个位置为0，则表示当前区间结束，需要将合并区间加入到答案中，并重置合并区间的起始点和结束点；如果当前位置为0且下一个位置为1，则表示当前区间开始，需要记录合并区间的起始点。\n\n最后，返回答案数组ans。\n\n代码分析完毕。"\n}