In another class of implementations, identifying (304) representative segments of a particular video sample may involve analyzing the time-varying encoding complexity of that video sample and selecting segments within the sample video having relatively high encoding complexity as the representative segments. As a particular example, a video sample may be broken up into segments of a common length, those segments encoded with a constant-quality constraint, and each of those encoded segments may be ranked by encoding complexity. Then, some fraction (e.g., 3%, 5%, 8%, 10%, 12%, 15%, 20%, etc.) of the segments having the highest encoding complexity may be selected as the representative segments. This type of approach, selecting the segments with the highest encoding complexity, may be a relatively conservative approach, in that it may ensure a minimum video quality for even the most complex scenes. Other approaches may also be implemented. As an example, the segments having an encoding complexity in the middle of the encoding complexity distribution may be selected (e.g., the segments having an encoding complexity greater than 45% of the other segments, while also having an encoding complexity less than 45% of the other segments). As another example, the segments having an encoding complexity near the bottom of the encoding complexity distribution may be selected (e.g., the segments having an encoding complexity less than 95%, 90%, etc. of the other segments).