Apt-get got there first. Debian does a pretty good job of trying to make upgrades work (which isn't really an apt thing, plenty of apt based distributions don't actually care to make upgrades work).
It's been a while, but my understanding is redhat figured out dependency resolution too, though.