DateInterval Min/Max performance issue

Bug introduced in 12.1 and persisting through 12.2.0

Update

WRI has confirmed that this is a bug. CASE:4521676

---

The performance of Min and Max on a list of DateInterval is O(2^n) where n is the length of the list.

$Version
(* 12.1.0 for Mac OS X x86 (64-bit) (March 14, 2020) *)

Generate some random date intervals

SeedRandom[11]; intervals = 30;

dateIntervals = 
 Table[DateInterval[{DateObject[{2019, 6, 15, 16, k = RandomInteger[{0, 59}]}], 
    DateObject[{2019, 6, 15, 16, RandomInteger[{k, 59}]}]}], intervals];

Timing Min for lengths 1 to 24. This takes ~5 min on my machine.

timings = Table[{n, dateIntervals // Take[#, n] & // Min // AbsoluteTiming // First}, {n, 1, 24}];

Fit 2^n

nlm = NonlinearModelFit[timings, b 2^n, {b}, n]

Show[ListLogPlot[timings], LogPlot[nlm[x], {x, 1, 24}]]

An easy workaround

dateIntervals // Map[Min] // Min

Strange that this simple operation would have performance issues.

Is this reproducible on other platforms?
Any other workaround ideas?

I have reported this to WRI.

$Version