If this is an real world abstrcted problem, i'd prefer to use divide and conquer technique depends on the requirements. For example, partitioning input intervals based on interval start/end value, i.e we have 1000 buckets, inside each bucket we maintain a sorted intervals, each bucket can be in one machine or multiples buckets in one machine. then we use merge those bucket 2 by 2 until to the point each bucket contains maximum intervals. And make sure no intervals are across two buckets