8:00 PM Oct. 5, 2020 - mock interview as an interviewee -

MaximumPeopleAlive.cs

using System;

// To execute C#, please define "static void Main" on a class
// named Solution.

/*
Persons[] 
birth year - death year [2000, 2020]
2000-2020
1999-2019
1965-2019
1989-2015
1966-1989
1965-1990
1954 - 
1954-1955
1989-2001

1954 - 2020
1954 - 2000 - check maximum birth year
-----------------
birth year/ end year
birth year +1
end year -1
keep maximum count 
year-> finish all 
people alive
max 
1954 +1
1955 -1
1965 +1
1965 +1
1966 +1
once -> year, +1, death -1 - 0, + 2
SortedDictionary< int, int> +1
hashMap<int, int> 
sorted  1954 - 2020 - 
Array - maximum range of time - bucket - declare - year earliest - latest year

 Sorted
 go through the array 
 O(N)
 sorted by year O(Nlogn)
 bucket - maximum M - O(M) - Maximum range of end year - start O(M), 2000 1954 - 2020   1900 - 2020 - 120 year
2000-2100
1400-2010
O(M) M = range 2100 - 1400?  700 years size - array 
O(M + N) - linear time complexity, 
1million - N million 
M - 700 years
space O(M)
space - sorted 
*/
class People {
    int by;
    int dy;
}

class Solution
{
    static void Main(string[] args)
    {
        for (var i = 0; i < 5; i++)
        {
            Console.WriteLine("Hello, World");
        }
    }
    
    // Peoples[]
    // year range from 1400 - 2100
    public int CountMax(Peoples[] people)
    {
        if(people == null || people.Length == 0)
            return 0; 
        
        var max = 0; 
        var count = 0;
        
        // 0 - 700
        // var yearCount = new int[2101]; // O(2 * N)
        var maxYear = int.MinValue;
        var minYear = int.MaxValue;        
        
        
        for(int i = 0; i < people.Count; i++)
        {
            var birthYear = people[i].by;
            var deathYear = people[i].dy;
            maxYear = Math.Max(max, deathYear);
            minYear = Math.Min(min, birthYear); 
        }
        
        var size = maxYear - minYear + 1; 
        var countYear = new int[size]; //M = size - size - remove redundancy - prune
        
        for(int i = 0; i < people.Count; i++)
        {
            var birthYear = people[i].by;
            var deathYear = people[i].dy;
            
            countYear[birthYear - minYear]++;
            countYear[deathYear - minYear]--;
        }
        
        // start from earliest time - go through 
        for(int i = 0; i < size; i++)
        {
            count += countYear[i];
            max = Math.Max(max, count); 
        }
        
        return max;                
    }
}