Discussion on: Algorithms: Common Years Problem

View post

Replies for: Hi Mohammed Shaikh, I want to contribute to your post to make it clearer and reach more reader. Firstly, about problem description, there is no rea...

Hi Nam H. Le,
I wanted to return 0 because there are no years overlapping. That was the original question. As for the modification of the problem statement, I am interested. What would be the problem statement. Let me know what you think 😃

Nam Hoang Le • Jun 25 '20

First of all, to avoid ambiguation, we assume that if a person born (or die), he will born in the first (last) day of that year.
My solution is to create two 2-tuple for each person: (start_year, 1) and (end_year, -1).
And this one has O(nlogn) complexity. I'm wrong in previous coment.

def find2 arr
  ans, max_count, curr_count = nil, 0, 0
  arr
  .flat_map {|start_year, end_year| [[start_year, 1], [end_year, -1]]}
  .sort {|(s1, e1), (s2, e2)| s1 != s2 ? s1 <=> s2 : e2 <=> e1}
  .each {|year, delta|
    curr_count += delta
    ans, max_count = year, curr_count if curr_count > max_count
  }
  ans
end

find2([[1,5], [5, 9], [2,7]]) #  => 5

# [1      5]
#        [5       9]
#   [2        7]


#           count
# [1, 1]  => 1 
# [2, 1]  => 2
# [5, 1]  => 3 : max
# [5,-1]  => 2
# [7, -1] => 1
# [9,-1]  => 0

Mohammed Shaikh • Jun 25 '20

Thanks Nam H. Le. That is an interesting variation of the problem