python题目练习 无重叠区间
sad本来想继续写糖果的 但是发现自己不会写 然后想写那个排列身高的 发现自己压根不知道这个怎么统筹 我真的泪目了 我试试写这个 如果这个再不会写 我真的破防
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
需要移除的区间的最小数量 看示例2 如果存在两个元素相等 那么一定是要进行剔除的 先将这个考虑进去 如果两个元素的第一个值相等 那么需要考虑第二个值
class Solution(object):def eraseOverlapIntervals(self, intervals):n=len(intervals)#首先将区间按照第一个元素先排序 然后第二个元素再排序的方式进行排序for i in range(n):for j in range(0,n-i-1):if intervals[j][0]>intervals[j+1][0]:temp=intervals[j]intervals[j]=intervals[j+1]intervals[j + 1]=tempif intervals[j][0]==intervals[j+1][0] and intervals[j][1]>intervals[j+1][1]:temp = intervals[j]intervals[j] = intervals[j + 1]intervals[j + 1] = temp#按照这种方式先将元素按照第一个元素优先的方式进行排序print(intervals)solution=Solution() result=solution.eraseOverlapIntervals([[2, 3], [1, 5], [2, 1], [1, 2]]) print(result)
好的 现在这些元素排好序了 然后就是进行去重 设置一个新数组 将不重复的元素写进来
class Solution(object):def eraseOverlapIntervals(self, intervals):n=len(intervals)#首先将区间按照第一个元素先排序 然后第二个元素再排序的方式进行排序for i in range(n):for j in range(0,n-i-1):if intervals[j][0]>intervals[j+1][0]:temp=intervals[j]intervals[j]=intervals[j+1]intervals[j + 1]=tempif intervals[j][0]==intervals[j+1][0] and intervals[j][1]>intervals[j+1][1]:temp = intervals[j]intervals[j] = intervals[j + 1]intervals[j + 1] = temp#按照这种方式先将元素按照第一个元素优先的方式进行排序print(intervals)num = [intervals[0]]for i in range(1,n):if intervals[i]!=intervals[i-1]:num.append(intervals[i])return num solution=Solution() result=solution.eraseOverlapIntervals([[2, 3], [1, 5], [2, 1],[2, 1], [1, 2]]) print(result)
好的 现在这个数组就是已经排好顺序 而且不包含重复元素了 那么现在就到了非常关键的了 如何去掉最少的区间使得这个数组是不重叠的呢？
[[1, 2], [1, 5], [2, 1], [2, 3]] 去掉最少的区间 就是保留数量最多的区间 那么要是想使得数量最多 是不是应该如果两个元素的起始点是一样的 那么是不是应该抛弃第二个元素值大的
就比如 1 2 、1 3、 1 5 如何使得没有重叠 这个必须要去掉两个 但是是不是如果去掉了 1 3 1 5 那么后续出现 2 开头就可以没有重叠 例如有 2 3 这样的就没有重叠
所以说数组中的元素 如果是第一个元素相同的 那么必然会存在重叠 那么只能去掉 而且去掉尾部元素值大的那个 好的 那么我们基于上面的代码继续往下面 我们再创建一个数组 我的想法过于简单了 想的就是如果第一个元素相等了 那么就只能选择一个 所以我就选择尾部最小的那个 从前往后选 代码如下
class Solution(object):def eraseOverlapIntervals(self, intervals):n=len(intervals)#首先将区间按照第一个元素先排序 然后第二个元素再排序的方式进行排序for i in range(n):for j in range(0,n-i-1):if intervals[j][0]>intervals[j+1][0]:temp=intervals[j]intervals[j]=intervals[j+1]intervals[j + 1]=tempif intervals[j][0]==intervals[j+1][0] and intervals[j][1]>intervals[j+1][1]:temp = intervals[j]intervals[j] = intervals[j + 1]intervals[j + 1] = temp#按照这种方式先将元素按照第一个元素优先的方式进行排序print(intervals)num = [intervals[0]]for i in range(1,n):if intervals[i]!=intervals[i-1]:num.append(intervals[i])print(num)num1=[num[0]]#怎么去掉元素呢？如果首部元素相等for i in range(1,len(num)):if num[i][0]==num[i-1][0]:continueelse:num1.append(num[i])print(num1)return n-len(num1)solution=Solution() result=solution.eraseOverlapIntervals([[1,100],[11,22],[1,11],[2,12]]) print(result)
但是在测试的时候又发现了一个问题
[[1,100],[11,22],[1,11],[2,12]]经过代码之后得到的是 [[1, 11], [2, 12], [11, 22]] 但是有木有发现 还是有重叠的 去的不够彻底 第一个元素是到11 第二个元素从2开始 那么还要去掉 比如我将 2 12 去掉之后的 1 11 和 11 22 这个才称得上是确实没重叠 那么这一步代码怎么写呢？
所以说我这个逻辑并不是完全正确 那么其实是不是按照结尾的如果大于下一个元素的起始的 就要将元素删去
1 11， 1,100, 2 12， 11 22如果是按照下一个开始的如果小于上一个结尾的 那么1 100删掉 之后就是1 11 ，2 12 ，11 22 然后2,12 也要删掉 剩下 1 11， 11，22 那么这个就是正常的了
所以没必要先删除首元素相同的 直接用下一个元素的第一个值如果小于上一个元素的后一个值 就删除 删除完之后 其实比较的对象还是这个元素 和删除之后前移的下一个元素 这样会导致很多元素移动 我觉得可能会超时 但是还是先试试
以下是代码
class Solution(object):
def eraseOverlapIntervals(self, intervals):
n=len(intervals)
#首先将区间按照第一个元素先排序 然后第二个元素再排序的方式进行排序
for i in range(n):
for j in range(0,n-i-1):
if intervals[j][0]>intervals[j+1][0]:
temp=intervals[j]
intervals[j]=intervals[j+1]
intervals[j + 1]=temp
if intervals[j][0]==intervals[j+1][0] and intervals[j][1]>intervals[j+1][1]:
temp = intervals[j]
intervals[j] = intervals[j + 1]
intervals[j + 1] = temp
#按照这种方式先将元素按照第一个元素优先的方式进行排序
print(intervals)
num = [intervals[0]]
for i in range(1,n):
if intervals[i]!=intervals[i-1]:
num.append(intervals[i])
print(num)
num1=[num[0]]
#怎么去掉元素呢？如果首部元素相等
#如果存在我说的那种情况 那么就删 直到不出现了 才继续往下走
i=1
while i<len(num):
if num[i][0]<num[i-1][1]:
del num[i]#将这个元素删除
#如果不是的话 那么才可以继续往下走
else:
i+=1
#但是我疑惑的是
print(num)
return n-len(num)
solution=Solution()
result=solution.eraseOverlapIntervals([[1,2],[1,3],[1,4]])
print(result)
然后天杀的 我又遇到了之前的问题 针对于这个del 我并不能很好地维护 又出现了之前的问题 啊啊啊啊 气死我了 换种方法 而且我的代码还有问题就是把重复去掉的元素没有算进去
那么我们想想如何得到删除的元素 是不是对于这个元素来说它的首元素小于上一个元素的尾巴元素 就要被删掉 然后其实这个元素被删掉的话 后面的元素会因为这个删除的元素受影响 后面的元素就不考虑这个删除的元素 而考虑删除元素之前的元素就行 所以pre 应该等于min(pre,num[i][1] 不然的话就是可以往下走了 那么pre等于Num[i][1]
比如 12,13,14 23 删掉13之后 pre应该还是12 但是如果到23这里不满足条件 那么pre就需要变成23了
我们保留的是结束时间更早的那个区间
为什么？因为结束得早，后面更容易不重叠（这是贪心策略）
如果没有重叠 那么当前的这个作为新的pre 之前该count的都计算完毕了
其实重叠没必要单写，虽然但是去掉 去掉重叠这部分代码还是超时 然后其实对于排序 没必要左边排完排右边 直接按照左边进行排序就行 对于左边排好顺序之后 其实右边现在我们对于多大是不知道的 但是我们从 第一个元素开始 如果第二个元素和左边元素比第一个元素的左边小 那么其实是有重叠的 所以我们计算重叠数目加一 那么接下来的元素是和谁进行比较呢？当然是和这两个的右边的元素更小的进行比较 也就是pre=min(prev,intervals[i][1]) 当然如何不满足条件 pre直接等于intervals[i][1] 注意别犯糊涂 i可是一直往下面走的
想想是不是这个道理 我们直接就是比如 1 6,1 2,2 3.对于第二个元素的12 1是不是小于6 那么count+1 然后对于下一个比较的 是不是其实应该跟12比 跟更小的那个比 发现诶 可以 那么直接将Pre换为 23就行 就是这个思路
class Solution(object):def eraseOverlapIntervals(self, intervals):n=len(intervals)#首先将区间按照第一个元素先排序 然后第二个元素再排序的方式进行排序for i in range(n):for j in range(0,n-i-1):if intervals[j][0]>intervals[j+1][0]:temp=intervals[j]intervals[j]=intervals[j+1]intervals[j + 1]=temp#按照这种方式先将元素按照第一个元素优先的方式进行排序#怎么去掉元素呢？如果首部元素相等count=0prev=intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] < prev:count += 1 # 有重叠，必须移除一个# 保留结束时间更早的那个区间（贪心策略）prev = min(prev,intervals[i][1])else:prev = intervals[i][1]return count solution=Solution() result=solution.eraseOverlapIntervals( [[1,2],[2,3],[3,4],[1,3]]) print(result)
然后还是超时 很可笑的是吧那个排序的方式改为 底下标红的方式就可以了
class Solution(object):def eraseOverlapIntervals(self, intervals):n=len(intervals)#首先将区间按照第一个元素先排序 然后第二个元素再排序的方式进行排序 intervals.sort(key=lambda x: x[1])#按照这种方式先将元素按照第一个元素优先的方式进行排序#怎么去掉元素呢？如果首部元素相等count=0prev=intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] < prev:count += 1 # 有重叠，必须移除一个# 保留结束时间更早的那个区间（贪心策略）prev = min(prev,intervals[i][1])else:prev = intervals[i][1]return count
solution=Solution()
result=solution.eraseOverlapIntervals( [[1,2],[2,3],[3,4],[1,3]])
print(result)所以说 意思就是排序的时候直接按照·左边排序就行 如果有重叠 coun+=1 然后下一个进行比较的去选择后面小的进行比较 在这个过程中i是一直在增加的 只有当不重叠的时候 才可以直接换下一个比较的元素 而不是进行Min的方法 （第一个元素相同，第二个元素不同）
泪目 灵活度真的太重要了 我的脑子能不能变得厉害点！