CODEWITHSUNDEEP
c#algorithmlinq
rahulaga-msft
rahulaga-msft

Reputation: 4164

algorithm to consolidate overlapping range

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.

Upvotes: 0

Views: 145

Answers (1)

Zohar Peled
Zohar Peled

Reputation: 82474

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 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."

Upvotes: 2

Related Questions