Frontend School

Calculate Effective Pricing Adjustments

DSA
hard

Calculate Effective Pricing Adjustments

Hard
Intervals
Sweep Line
Greedy

Overview

Airbnb hosts often apply various pricing rules to their listings for specific date ranges, such as seasonal discounts, weekend surcharges, or event-specific pricing. These rules can overlap, and when they do, their effects combine. Your task is to process a list of such pricing adjustment intervals and determine the net effective adjustment for every contiguous period of time.

What you need to do / Task

Given a list of pricing adjustment intervals, each defined by a start date, an exclusive end date, and an integer adjustment value, you must:

  1. Aggregate all overlapping adjustments for any given day.
  2. Generate a new list of non-overlapping intervals, where each interval represents a contiguous period with a constant total effective adjustment value.

Input & output

Input: adjustments: An array of arrays, where each inner array [start, end, value] represents a pricing adjustment interval.

  • start: An integer representing the inclusive start day of the adjustment.
  • end: An integer representing the exclusive end day of the adjustment. (i.e., the adjustment applies up to, but not including, end).
  • value: An integer representing the absolute adjustment amount (e.g., +10 for a $10 increase, -5 for a $5 discount).

Output: An array of arrays, effectiveAdjustments, where each inner array [effectiveStart, effectiveEnd, totalValue] represents a non-overlapping interval with its aggregated adjustment value.

  • The output intervals must be sorted by effectiveStart in ascending order.
  • effectiveEnd is exclusive, matching the input interval semantics.
  • All days where at least one adjustment applies should be covered. If the total adjustment for a period is 0, it should still be included in the output if it forms a distinct segment.

Clarifications

  • Empty Input: If adjustments is empty, return an empty array.
  • Date Range: The start and end dates can be very large integers, implying that a direct array/map indexed by day is not feasible.
  • Output Consistency: Ensure the output intervals are strictly non-overlapping and sorted, covering all affected time segments.

Examples

1

Example 1

Input:

adjustments = [[0, 5, 10], [3, 7, -5]]

Output:

[[0,3,10],[3,5,5],[5,7,-5]]

Note:

Days [0,3) have only +10. Days [3,5) have +10 and -5, totaling +5. Days [5,7) have only -5.

2

Example 2

Input:

adjustments = [[1, 4, 10], [2, 5, -5], [3, 6, 20]]

Output:

[[1,2,10],[2,3,5],[3,4,25],[4,5,15],[5,6,20]]

Note:

Events at day 1: +10. Day 2: +10-5=5. Day 3: +10-5+20=25. Day 4: -5+20=15. Day 5: +20.

3

Example 3

Input:

adjustments = [[0, 10, 5], [2, 8, -5]]

Output:

[[0,2,5],[2,8,0],[8,10,5]]

Note:

Days [0,2) have +5. Days [2,8) have +5 and -5, totaling 0. Days [8,10) have only +5.

Constraints

Constraints & assumptions

  • 0 <= adjustments.length <= 10^5
  • For each [start, end, value] in adjustments:
    • 0 <= start < end <= 10^9
    • -1000 <= value <= 1000
  • All dates are integers.

Out of scope

  • Handling non-integer date values.
  • Validating input for start >= end (assume valid intervals are provided).

What interviewers evaluate

  • Ability to model and solve problems involving overlapping intervals efficiently.
  • Correct application of data structures and algorithms (e.g., sweep line or event-point approach).
  • Precision in handling interval boundary conditions (inclusive/exclusive ends).
  • Correct aggregation logic for overlapping intervals.
  • Clarity and correctness of code, including edge cases and complexity considerations.

Loading editor...