Hmm... If you sort everyone's births and deaths you can just walk through the array keeping track of the number of people alive at each point and the maximum n

Hmm... If you sort everyone's births and deaths you can just walk through the array keeping track of the number of people alive at each point and the maximum number of people alive at any point (and the year(s) thereof). O(P log P) (from the sort), no explicit dependance on R. Are there any other good solutions? I cannot imagine that there would be anything that's sublinear in P, so about the only other thing I could imagine would be something that is linear in P and sublinear in R.