Runtime of weighted interval scheduling dynamic programming algorithm
If I understand your concern correctly, you are right in that many $p(j)$ may give the same $i$. But that means that other $i$s don't get many $p(j)$s (the total of them is $n$).