POJ 1089 Intervals -Python

POJ 1089 Intervals -Python

POJ 1089 Intervals

POJ 1089 Intervals

问题简单描述
n个闭区间,最终合并成一组闭区间

思路
全排序,然后逐一合并
重合判定
合并
排序(仅考虑区间下界)

问题
冒泡排序法时间复杂度,导致超时
改用Python的sorted函数

通过的方案

1.def custom_key(I_1):
2. return int(I_1[0])
3.N=int(input())
4.list_Intervals=[]
5.for i in range(N):
6. str_input=input()
7. list_Intervals.append([int(temp) for temp in str_input.split()])
8.list_Intervals.sort(key=custom_key)
9.I_min=list_Intervals[0]
10.for i in range(N-1):
11. if I_min[1]<list_Intervals[i+1][0]:
12. print(I_min[0],I_min[1])
13. I_min=list_Intervals[i+1]
14. else:
15. if I_min[1]<list_Intervals[i+1][1]:
16. I_min[1]=list_Intervals[i+1][1]
17.print(I_min[0],I_min[1])

问题
Python用空格分隔输入的数字
使用split():

1.N=int(input())
2.dict_Intervals={}
3.for i in range(N):
4. str_input=input()
5. dict_Intervals[i]=[int(temp) for temp in str_input.split()]

python实现方案超时

1.def TestIntersecting(I_1,I_2):
2. flag=0
3. if I_1[0]<=I_2[0]:
4. if I_1[1]>=I_2[0]:
5. flag=1
6. else:
7. if I_1[0]<=I_2[1]:
8. flag=1
9. return flag
10.def ADD(I_1,I_2):
11. I_Result=I_1
12. if I_1[0]>I_2[0]:
13. I_Result[0]=I_2[0]
14. if I_1[1]<I_2[1]:
15. I_Result[1]=I_2[1]
16. return I_Result
17.def SORT(I_1,I_2):
18. if I_1[0]<I_2[0]:
19. return I_1+I_2
20. else:
21. return I_2+I_1
22.def Bubble_SORT(n,dict_Intervals):
23. for i in range(n):
24. for j in range(n-1-i):
25. I_1=dict_Intervals[j]
26. I_2=dict_Intervals[j+1]
27. temp_Sort=SORT(dict_Intervals[j],dict_Intervals[j+1])
28. dict_Intervals[j]=[temp_Sort[0],temp_Sort[1]]
29. dict_Intervals[j+1]=[temp_Sort[2],temp_Sort[3]]
30. return dict_Intervals
31.N=int(input())
32.dict_Intervals={}
33.for i in range(N):
34. str_input=input()
35. dict_Intervals[i]=[int(temp) for temp in str_input.split()]
36.
37.dict_Intervals=Bubble_SORT(N,dict_Intervals)
38.I_min=dict_Intervals[0]
39.for i in range(N-1):
40. if TestIntersecting(I_min,dict_Intervals[i+1]) == 0:
41. print(I_min[0],I_min[1])
42. I_min=dict_Intervals[i+1]
43. else:
44. I_min=ADD(I_min,dict_Intervals[i+1])
45.print(I_min[0],I_min[1])

依旧超时的版本。。

1.N=int(input())
2.dict_Intervals={}
3.for i in range(N):
4. str_input=input()
5. dict_Intervals[i]=[int(temp) for temp in str_input.split()]
6.for i in range(N):
7. for j in range(N-1-i):
8. if dict_Intervals[j][0]>dict_Intervals[j+1][0]:
9. temp=[dict_Intervals[j+1][0],dict_Intervals[j+1][1]]
10. dict_Intervals[j+1]=dict_Intervals[j]
11. dict_Intervals[j]=temp
12.I_min=dict_Intervals[0]
13.for i in range(N-1):
14. if I_min[1]<dict_Intervals[i+1][0]:
15. print(I_min[0],I_min[1])
16. I_min=dict_Intervals[i+1]
17. else:
18. if I_min[1]<dict_Intervals[i+1][1]:
19. I_min[1]=dict_Intervals[i+1][1]
20.print(I_min[0],I_min[1])

发表评论

电子邮件地址不会被公开。 必填项已用*标注