I've been trying to solve a scheduling problem for a couple of days that involves searching to find the union and the intersection between sets.
I have managed to solve the problem with small sets, but when the set starts getting very large, however much the program arrives in the response, I get a Time limit exceeded.
I made a similar program in c ++ and the code was accepted, but in python it just did not pass ...
I've optimized my program as much as possible, but the runtime has not changed enough ...
My question is:
- Is there any way to further reduce runtime with python programs?
The problem comes down to given a number of sets. For example
Set 1: - > 1 1
Set 2: - > 2 1 5
Set 3: - > 3 2 4 6
Set 4: > 4 1 3 5 7
And given certain operations between sets return:
(1: Number of elements other than the intersection)
(2: Number of distinct elements of the union)
Example operations:
Case 1: - > 1 1 2 (Intersection between set 1 and set 2)
Case 2: - > 2 1 4 (Union between set 1 and set 4)
Case 3: - > 1 3 4 (Intersection between set 3 and set 4)
Case 4: - > 2 2 4 (Union between set 2 and set 4)
Program I did:
def main():
# Casos de Teste
for i in range(int(input())):
lis = []
# Quantidade de Conjuntos
for j in range(int(input())):
# Lista com todos os números do conjunto
lis.append(list(map(int, input().split())))
# O primeiro elemento é a quantidade de números do
conjunto
lis[j].pop(0)
# Quantidade de operçãoes
for j in range(int(input())):
# Operação e conjuntos escolhidos
op, l1, l2 = map(int, input().split())
# Interseção
if(op == 1):
# -1 por conta do index da lista
inte = set(lis[l1-1]) & set(lis[l2-1])
print(len(inte))
# União
else:
union = set(lis[l1-1]) | set(lis[l2-1])
print(len(union))
if __name__ == "__main__":
main()
The link to the question is: link