## DEV Community is a community of 793,259 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Discussion on: Algorithms: Common Years Problem

## Replies for: 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 s...

Nam Hoang Le

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
``````