# An integer interval [a,b], Find the minimum size of a set S.

An integer interval [a,b] (for integers a < b) is a set of all consecutive integers from a to b, including a and b. Find the minimum size of a set S such that for every integer interval A in intervals, the intersection of S with A has size at least 2.

Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3

def intersection(intervals):
intervals = sorted(intervals, key=lambda x: (x[0],-x[1]))
todo = [2] * len(intervals)
ans = 0
while intervals:
(s, e), t = intervals.pop(), todo.pop()
for p in range(s, s+t):
for i, (s0, e0) in enumerate(intervals):
if todo[i] and p <= e0:
todo[i] -= 1
ans += 1
return ans
N=int(input("Enter the N number of set intervals: "))
print('Enter the sets: ')
list1=[]
for i in range(N):
list1.append(list(map(int,input('--> ').split(' '))))
print("Intervals = {}".format(list1))

print('Minimum Size of set S: ',intersection(list1))

Sample Inputs… ?
Input_1:
Enter the N number of set intervals: 4
Enter the sets:
–> 1 3
–> 1 4
–> 2 5
–> 3 5
Output:
Intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
Minimum Size of set S: 3

Input_2:
Enter the N number of set intervals: 3
Enter the sets:
–> 8 10
–> 2 4
–> 4 5
Output:
Intervals = [[8, 10], [2, 4], [4, 5]]
Minimum Size of set S: 5

Input_3:
Enter the N number of set intervals: 10
Enter the sets:
–> 2 10
–> 3 7
–> 3 15
–> 4 11
–> 6 12
–> 6 16
–> 7 8
–> 7 11
–> 7 15
–> 11 12
Output:
Intervals = [[2, 10], [3, 7], [3, 15], [4, 11], [6, 12], [6, 16],                                        ,[7, 8], [7, 11], [7, 15], [11, 12]]
Minimum Size of set S: 5

Input_4:
Enter the N number of set intervals: 4
Enter the sets:
–> 1 2
–> 2 3
–> 3 4
–> 4 5
Output:
Intervals = [[1, 2], [2, 3], [3, 4], [4, 5]]
Minimum Size of set S: 5

Exec. on terminal

More Codes to Fcuk