I wrote a piece of code and seems to be working, but since I'm relatively new to algorithms, I'm not sure whether it's done correctly. Even if it's not the most efficient.
The code pretty much checks whether each year falls between the birthyear and deathyear of each scientist, if it does, it increments count by 1.
Scientist.cs
public class Scientist
{
public string Name { get; set; }
public int Birthdate { get; set; }
public int Deatdate { get; set; }
public Scientist(string name, int bDate, int dDate)
{
this.Name = name;
this.Birthdate = bDate;
this.Deatdate = dDate;
}
}
A sample of what the list contains
List<Scientist> scientists = new List<Scientist>()
{
new Scientist("Albert Einstein", 1879, 1955),
new Scientist("Alessandro Volta", 1745, 1827),
new Scientist("Alexander Fleming", 1881, 1955),
new Scientist("Alexander Graham Bell", 1847, 1922),
new Scientist("Alfred Nobel", 1833, 1896),
new Scientist("Amedeo Avogadro", 1776, 1856),
new Scientist("André-Marie Ampère", 1775, 1836),
new Scientist("Antoine Henri Becquerel", 1852, 1908),
new Scientist("Antoine Lavoisier", 1743, 1794),
new Scientist("Blaise Pascal", 1623, 1662),
new Scientist("Carl Friedrich Gauss", 1777, 1855),
new Scientist("Carl Sagan", 1934, 1996),
new Scientist("Charles Darwin", 1809, 1882),
new Scientist("Charles-Augustin de Coulomb", 1736, 1806),
new Scientist("Edwin Hubble", 1889, 1953),
};
Program.cs
List<int> years = new List<int>();
List<int> count = new List<int>();
int minYear = scientists.Min(s => s.Birthdate);
int maxYear = scientists.Max(s => s.Deatdate);
for (int i = minYear; i < maxYear 1; i )
{
years.Add(i);
count.Add(0);
}
foreach (Scientist s in scientists)
{
for (int i = 0; i < years.Count - 1; i )
{
if (years[i] > s.Birthdate && years[i] < s.Deatdate)
{
count[i] = 1;
}
}
}
CodePudding user response：
As the saying goes, there's more than one way to skin a cat. Your method works ... my only correction would be the last part of your code. You don't include the last year in your iteration and your test condition does not include the birth year or death year. To correct, use the following
foreach (Scientist s in scientists)
{
for (int i = 0; i < years.Count; i )
{
if (years[i] >= s.Birthdate && years[i] <= s.Deatdate)
{
count[i] = 1;
}
}
}
Another method you could use is to create a list of beginning and ending years, including a count: List<(int BeginYear, int EndYear, int Count)>. Then, iterate through the scientists, modifying this list as needed. Example:
List<(int BeginYear, int EndYear, int Count)> list = new List<(int BeginYear, int EndYear, int Count)>();
foreach (var scientist in scientists)
{
for (int i = 0; ; i )
{
if (i < list.Count)
{
// extract information from list
(int beginYear, int endYear, int count) = list[i];
if (scientist.Birthdate <= beginYear)
{
// scientist born before or same time as previously processed scientists
if (scientist.Deatdate < beginYear)
{
// scientist also died before previously processed scientists, insert scientists years in list
list.Insert(i, (BeginYear: scientist.Birthdate, EndYear: scientist.Deatdate, Count: 1));
if (scientist.Deatdate 1 < beginYear)
{
// insert years into list where no scientist alive
i ;
list.Insert(i, (BeginYear: scientist.Deatdate 1, EndYear: beginYear - 1, Count: 0));
}
break;
}
else
{
if (scientist.Birthdate < beginYear)
{
// add years for birth
list.Insert(i, (BeginYear: scientist.Birthdate, EndYear: beginYear - 1, Count: 1));
i ;
}
// increment following years
for (; ; i )
{
if (i < list.Count)
{
(beginYear, endYear, count) = list[i];
if (endYear <= scientist.Deatdate)
{
// scientist still alive; increment and continue?
list[i] = (beginYear, endYear, count 1);
if (endYear == scientist.Deatdate) break; // don't need to continue if died at last year in range
}
else
{
// scientist dies within year range; split year range and increment portion where scientist was alive
list[i] = (scientist.Deatdate 1, endYear, count);
list.Insert(i, (BeginYear: beginYear, EndYear: scientist.Deatdate, Count: count 1));
break;
}
}
else
{
// scientist died after others; EndYear is last date other scientist was alive
list.Add((BeginYear: endYear 1, EndYear: scientist.Deatdate, Count: 1));
break;
}
}
}
}
else if (scientist.Birthdate <= endYear)
{
// scientist born during current range of years; split and loop once more to enable above code to process
list[i] = (scientist.Birthdate, endYear, count);
list.Insert(i, (BeginYear: beginYear, EndYear: scientist.Birthdate - 1, Count: count));
}
}
else
{
// list empty or scientist born after previously processed scientists all died
if (i > 0)
{
// add buffer of years with no scientist alive, if needed
(int beginYear, int endYear, int count) = list[i - 1];
if (endYear 1 < scientist.Birthdate)
{
list.Add((BeginYear: endYear 1, EndYear: scientist.Birthdate - 1, Count: 0));
}
}
list.Add((BeginYear: scientist.Birthdate, EndYear: scientist.Deatdate, Count: 1));
break;
}
}
}
// finally, sort the list so the year ranges with the most scientists alive come first
list.Sort(new Comparison<(int BeginYear, int EndYear, int Count)>((l1, l2) => l2.Count - l1.Count));
As to what's the most "efficient", that depends on what you want to do with the data.
CodePudding user response：
Another cat (a LINQs, perhaps)
var min = scientists.Min(s => s.Birthyear);
var maxLive =
Enumerable.Range(min, scientists.Max(s => s.Deatdate) - min 1)
.Select(yr => new { Yr = yr, Ct = scientists.Count(s => yr >= s.Birthdate && yr <= s.Deatdate)})
.MaxBy(at => at.Ct)
.Yr;
It's the same as your approach - Enumerable.Range generates a list of all the years from first birth to last death, the Select counts the number of people alive in each year and stashes the year and the count in an anonymous type, then the list of anonymous types is max's on the count and the year is pulled from the item with the max
Here's another one:
scientists
.SelectMany(s => Enumerable.Range(s.Birthdate, s.Deatdate - s.Birthdate 1))
.GroupBy(yr => yr)
.MaxBy(lu => lu.Count())
.Key;
similar approach; we convert every scientist into a list of years (so it a scientist was born 1970 and died 1999 it becomes a sequence of 29 ints from 1970 to 1999). The SelectMany unpacks each list of years that each scientist lived into just one long list of years (so if there were 3 people from 1990 to 1992, 1991 to 1993 and 1992 to 1994, a single list of 1990,1991,1992,1991,1992,1993,1992,1993,1994 is realized). This list of years is then grouped on the year, effectively turning it back into a list of lists where we can count the items to know how many times each year appeared (e.g. 1992 appears thrice). Calling MaxBy on the count returns a maximum grouping and the grouping's key is the year
The question doesn't specify what to do when we're tied on Years - there are quite a few years in your list where 6 people are alive