算法-集合划分问题

Question

想要完成一个连续集合的划分问题，大概情况是
有连续数1-100。作为一个全集。然后有许多子集合，例如[5-10]，[2-25]想要，子集合会相交。然后要把这个1-100划分开。划分为很多块，然后用序号1 2 3.。。去标识。
例如上述情况会被划分会[1-1]、[2-5]、[6-10]、[11-25]、[26-100]。然后分别标识为1 2 3 4 5.求思路

Answer 1

算法如下：
1.把所有的子集合的首尾两个数字提取出来，加上1和100两个数字，总共组成一个大的数集，然后从小到大排序
2.每两个相邻的数字划分成一个集合。注意，这个集合的划分有闭集合("[]")和开集合("()")之分。那么在划分子集的时候，规律是这样的：
1)总集合的1和100两个数字一定是闭集合。
2)子集合的首数字前开后闭。子集合的尾数字前闭后开。例如:原题中数集是1,2,5,10,25,100.对于子集合[5,10]，5是首数字，则划分的时候前面划分的子集使用开括号，即[2,5).而后面划分的子集使用闭括号，即[5,10).其他同理。
如果想要知道某个子集是由哪些划分子集组成的，只需要找出该子集的首尾数字区间之间的划分子集即可，而这个搜索一遍划分子集就OK了。
对于楼主的示例，算法过程如下：
1.提取所有子集合的首尾数字和1和100并排序，则得到1,2,5,10,25,100。
2.根据上一步的结果，则划分子集为[1,2),[2,5),[5,10],(10,25],(25,100]。(注意开闭括号)

Answer 2

换个角度看,这是一个无向图.两个点属于一个子集的含义就是两个顶点是连通的.因此这个题目就是要找出图中的所有联通分量. 只要按照标准的深度优先算法就可以了.

Answer 3

有个想法，可能时空复杂度会差些，但是可以实现要求的功能：
第一步：将所有的集合按照下界从小到大进行编号
第二步：从小到大依次扫描全集，然后从当前下界最小集合开始取数，每取一个数判断当前数是否属于另外一个集合，若不属于则继续取数，若属于则重新设定此集合上界，而此集合剩余部分重新加入集合序列，加按照下界从小到大排序；如此重复，直到所有集合序列中没有集合为止
至于标识则很简单了，从小到大标识就可以了