Hi Guys, last week I participated in an internal hackathon at my Internship and I couldn’t resolve this problem. I did my solution, but it not run in expected time. Can someone help me improve the code:
There are n animals placed in straight line. Each animal is identified by a unique number from 1 to n. There ae m pairs (a[i], b[i]) which imply that animals a[i] and b[i] are enemies and should not be kept in the same cabin. Count the number of different groups that do not contain any pair such that they are enemies. A group is defined as an interval (x,y) such that all animals in the range from x to y form a group. The animals cannot be reordered and cannot be skipped, e.g, [3,2,1] and [1,2,4] are invalid intervals
Function Description
Complete the AngryAnimals function. The function should return the number of formed groups:
Parameters:
n: denotate the number of uniq animals
a: array of integers
b: array of integers
Constraints
1 <= n <= 10^5
1 <= m <= 10^6
1 <= a[i], b[i] <= n
Sample case 1
n = 4
a = [2,1,2]
b = [2,3,4]
Expected output: 7
Explanation: [1], [2], [3], [4], [1,2] [2,3], [3,4] are the valids groups
Sample case 2
n = 5
a = [2,1,2]
b = [2,3,5]
Expected Output: 11
Explanation: [1], [2], [3], [4], [5], [1,2], [2,3], [3,4], [4,5], [2,3,4], [3,4,5] are the valid groups
Now my code
def combinations(n)
combinations = 0
elements = (1..n).to_a
elements.each_index do |i|
(elements.length - i).times do |j|
combination = elements[j, i + 1]
# add the combination if no block is given, or if it evaluates to truthy
combinations += 1 if !block_given? || yield(combination)
end
end
combinations
end
def angryAnimals(n, *not_allowed)
# Write your code here
not_allowed = not_allowed.transpose.reject { |n| n[0] == n[1] }.map { |n| n.to_set }
combinations(n) do |combination|
combination = combination.to_set
not_allowed.reject { |set| set.size > combination.size }
.none? { |set| (set - combination).empty? }
end
end
Can someone help me please?