Maximum Highway Billboard Revenue
Updated
Problem statement
Candidate billboard i is at positions[i] on a highway from 0 through roadLength, and earns revenue[i]. Select any subset of candidates to maximize total revenue.
Every pair of selected billboards must be more than gap units apart. A distance exactly equal to gap is not allowed. Positions are distinct but may be supplied in any order. Return the greatest total revenue; selecting none earns 0.
Function
maximumBillboardRevenue(roadLength: int, positions: int[], revenue: int[], gap: int) → intExamples
Example 1
roadLength = 20positions = [2,8,9,10,15]revenue = [20,50,10,30,5]gap = 5return = 75Choose sites 2,8,15 for revenue 20+50+5=75. Consecutive distances 6 and 7 both exceed 5.
Example 2
roadLength = 10positions = [1,6]revenue = [4,7]gap = 5return = 7Distance 5 is forbidden, so choose only the higher-revenue site.
Constraints
1 <= roadLength <= 1000000.0 <= positions.length, revenue.length <= 2000.0 <= positions[i], revenue[i], gap <= 1000000.- positions and revenue have equal lengths.
- All candidate positions are distinct and at most roadLength.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Maximum Total Length of Non-Overlapping IntervalsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Russian Doll EnvelopesGoogle · ONSITE INTERVIEWGoogle interview questions
- Russian Doll EnvelopesInMobi · ONSITE INTERVIEWInMobi interview questions
- Fill a Time Window with SongsMicrosoft · OAMicrosoft interview questions
- Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
- Weighted Jobs from an Encoded Test CaseJP Morgan Chase · OAJP Morgan Chase interview questions
- Maximum Profit in Job SchedulingAmazon · PHONE SCREEN
- Maximum Event Value with an Attendance LimitSnowflake · PHONE SCREENSnowflake interview questions
- 3Sum SmallerSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Maintain a Consistent-Hashing RingCohesity · ONSITE INTERVIEW
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)