algorithm to consolidate overlapping range

Question

I have an offer configured with discount values and applicable volume range.

Its possible multiple offers applicable for a product, so I am looking for algorithm to consolidate overlapping volume range among various offers and show final discount applicable. Below code snippet would help to visualize the ask :

class VolumeTierRange
    {
        public int Min { get; set; }
        public int Max { get; set; }
        public int Discount { get; set; }
    } 

/* Offer1Range */
    List<VolumeTierRange> Offer1Ranges = new List<VolumeTierRange>{
                        new VolumeTierRange {Min=1,   Max=20,   Discount=2 },
                        new VolumeTierRange {Min=21,  Max=49 ,  Discount=10 },
                        new VolumeTierRange {Min=50,  Max=100 , Discount=5 },
                        new VolumeTierRange {Min=101, Max=1000, Discount=15}
                    };

/* Offer2Range */
List<VolumeTierRange> dicountBRanges = new List<VolumeTierRange>{
                new VolumeTierRange {Min = 1, Max=50,   Discount=6},
                new VolumeTierRange {Min=51,  Max=1000, Discount=10 }
            };

Consolidated result would look like :

List<VolumeTierRange> effectiveDiscount = new List<VolumeTierRange>{
                new VolumeTierRange {Min=1,  Max=20,  Discount=8 },
                new VolumeTierRange {Min=21, Max=49,  Discount=16},
                new VolumeTierRange {Min=50, Max=50,  Discount=11},
                new VolumeTierRange {Min=51, Max=100, Discount=15},
                new VolumeTierRange {Min=101,Max=1000,Discount=25}
            };

I do have some ways to achieve the expected outcome, but those all does not seems to be very intuitive.

Additional Info: Min value of first item and Max value of all offers is fixed (like 1 and 1000 in this example). Also there cannot be discontinuity while defining volume range.

"I do have some ways to achieve the expected outcome" You should *show* what you´ve tried, in order to avoid anybody oisting the same solution you already have. — MakePeaceGreatAgain, Mar 12 '18 at 07:35
So you need to intersect integer ranges and add a couple of discounts up. What's stopping you? — Manfred Radlwimmer, Mar 12 '18 at 07:37
@HimBromBeere : I can post what i tried but its going to clutter code and overall ask. Its nothing fancy : I did sorting on range min and max values and then tried to create chunk of overlapping ranges. Also its failing certain edge case scenarios, hence posted here. — rahulaga-msft, Mar 12 '18 at 07:43
Then those failing edge-cases are of upmost interest. How would you know if *any* of the solutions matches thoses cases where you failed? How should *we* know what works for you and what not? — MakePeaceGreatAgain, Mar 12 '18 at 07:45

Zohar Peled · Accepted Answer · 2018-03-12T08:50:32.657

Well, the first thing you want to do is figure out what values in Offer1Ranges overlap what values in dicountBRanges.
Items overlap when the min value of the first item is less then (or equal*) to the max value of the second item, while the min value of the second item is less then (or equal*) to the max value of the first item. For more information, see the overlap tag info.

Once you've joined the lists based on the overlapping items, it's a simple enough select to get the biggest of the two min values, the smallest of the two max values, and the sum of the discount value for each item:

var query = from o in Offer1Ranges
            from d in dicountBRanges
            where o.Min <= d.Max
            && o.Max >= d.Min
            select new VolumeTierRange()
            {
                Min = (o.Min > d.Min) ? o.Min : d.Min,
                Max = (o.Max < d.Max) ? o.Max : d.Max,
                Discount = o.Discount + d.Discount
            };

You can see a live demo or rextester.

*In your case, you consider the items overlapping even if it's on a single point (min of first equals the max of second or vice versa). This is not the general case.

Please note: This solution will only work as long as both lists starts and ends in the same numbers, and there are no gaps, as stated in the question:

"Additional Info: Min value of first item and Max value of all offers is fixed (like 1 and 1000 in this example). Also there cannot be discontinuity while defining volume range."

Thanks !! This looks cleaner. Can this be modified to not limit to only two specific offer ranges. I can have any numbers of offer applicable for product. — rahulaga-msft, Mar 12 '18 at 09:10
Probably... [check this SO post.](https://stackoverflow.com/questions/14984879/join-unknown-number-of-lists-in-linq) — Zohar Peled, Mar 12 '18 at 09:11

algorithm to consolidate overlapping range

1 Answers1