jorgedjr21
Oct '19

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?