We compare the structure of star-forming molecular clouds in different regions of Orion A to determine how the column density probability distribution function (N-PDF) varies with environmental conditions such as the fraction of young protostars. A correlation between the N-PDF slope and Class 0 protostar fraction has been previously observed in a low-mass star-formation region (Perseus) by Sadavoy; here we test if a similar correlation is observed in a high-mass star-forming region. We use Herschel data to derive a column density map of Orion A. We use the Herschel Orion Protostar Survey catalog for accurate identification and classification of the Orion A young stellar object (YSO) content, including the short-lived Class 0 protostars (with a $∼$ 0.14 Myr lifetime). We divide Orion A into eight independent 13.5 pc$^2$ regions; in each region we fit the N-PDF distribution with a power-law, and we measure the fraction of Class 0 protostars. We use a maximum likelihood method to measure the N-PDF power-law index without binning. We find that the Class 0 fraction is higher in regions with flatter column density distributions. We test the effects of incompleteness, YSO misclassification, resolution, and pixel-scale. We show that these effects cannot account for the observed trend. Our observations demonstrate an association between the slope of the power-law N-PDF and the Class 0 fractions within Orion A. Various interpretations are discussed including timescales based on the Class 0 protostar fraction assuming a constant star-formation rate. The observed relation suggests that the N-PDF can be related to an "evolutionary state" of the gas. If universal, such a relation permits an evaluation of the evolutionary state from the N-PDF power-law index at much greater distances than those accesible with protostar counts. (abridged) ; Comment: A&A Letter, accepted