Maximize the Profit as the Salesman - Practice Coding Problems

Maximize the Profit as the Salesman - Problem

You are given an integer n representing the number of houses on a number line, numbered from 0 to n - 1.

Additionally, you are given a 2D integer array offers where offers[i] = [start_i, end_i, gold_i], indicating that the i^th buyer wants to buy all the houses from start_i to end_i for gold_i amount of gold.

As a salesman, your goal is to maximize your earnings by strategically selecting and selling houses to buyers.

Return the maximum amount of gold you can earn.

Note: Different buyers can't buy the same house, and some houses may remain unsold.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, offers = [[0,2,1],[1,3,2],[3,4,3]]

› Output: 4

💡 Note: Select offers [0,2,1] and [3,4,3]. Houses 0-2 sold for 1 gold, houses 3-4 sold for 3 gold. Total = 1 + 3 = 4 gold.

Example 2 — No Overlaps

$ Input: n = 6, offers = [[0,1,2],[2,3,3],[4,5,4]]

› Output: 9

💡 Note: All offers are non-overlapping, so select all: 2 + 3 + 4 = 9 gold.

Example 3 — Single Best Offer

$ Input: n = 3, offers = [[0,2,10],[1,2,1]]

› Output: 10

💡 Note: Choose the single high-value offer [0,2,10] for maximum profit of 10 gold.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ offers.length ≤ 10⁵
offers[i].length == 3
0 ≤ start_i ≤ end_i ≤ n - 1
1 ≤ gold_i ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Input

Houses 0 to n-1 and buyer offers [start, end, gold]

Constraint

No house can be sold to multiple buyers

Optimize

Select offers that maximize total gold earned

Key Takeaway

🎯 Key Insight: This is weighted interval scheduling - sort by end time and use DP with binary search

Asked in

A Amazon 15 G Google 12 M Microsoft 8 🍎 Apple 6

This is a weighted interval scheduling problem. The key insight is to sort offers by end position and use dynamic programming. For each offer, we decide whether to include it (and add the best solution for non-overlapping previous offers) or exclude it. The optimal approach uses binary search to find previous non-overlapping offers in O(log m) time. Time: O(m log m), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^m × m)	O(m)	Generate all possible combinations of non-overlapping offers and find the maximum profit
Dynamic Programming with Sorting	O(m²)	O(m)	Sort offers by end position and use DP to build optimal solution incrementally
DP with Binary Search Optimization	O(m log m)	O(m)	Sort offers by end position and use binary search to quickly find the latest non-overlapping offer

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible subsets of offers
For each subset, check if offers overlap
Calculate total profit for valid subsets
Return maximum profit found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all possible combinations of offers

Check Overlaps

Validate each combination for house conflicts

Find Maximum

Track the highest profit among valid combinations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int maxProfit = 0;

int overlaps(int* offer1, int* offer2) {
    return !(offer1[1] < offer2[0] || offer2[1] < offer1[0]);
}

void backtrack(int offers[][3], int m, int index, int selected[][3], int selectedCount, int currentProfit) {
    if (index == m) {
        if (currentProfit > maxProfit) {
            maxProfit = currentProfit;
        }
        return;
    }
    
    // Skip current offer
    backtrack(offers, m, index + 1, selected, selectedCount, currentProfit);
    
    // Try to include current offer if no overlap
    int canInclude = 1;
    for (int i = 0; i < selectedCount; i++) {
        if (overlaps(offers[index], selected[i])) {
            canInclude = 0;
            break;
        }
    }
    
    if (canInclude) {
        for (int i = 0; i < 3; i++) {
            selected[selectedCount][i] = offers[index][i];
        }
        backtrack(offers, m, index + 1, selected, selectedCount + 1, currentProfit + offers[index][2]);
    }
}

int solution(int n, int offers[][3], int m) {
    maxProfit = 0;
    int selected[1000][3];
    backtrack(offers, m, 0, selected, 0, 0);
    return maxProfit;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[a,b,c],[d,e,f],...]
    int offers[1000][3];
    int m = 0;
    
    char* ptr = line + 1; // skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            offers[m][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            offers[m][1] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            offers[m][2] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            m++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(n, offers, m));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^m × m)

2^m subsets to check, each requiring O(m) time to validate overlaps

✓ Linear Growth

Space Complexity

O(m)

Recursion stack depth up to m offers

✓ Linear Space

21.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler