Number of Sets of K Non-Overlapping Line Segments - Problem

Given n points on a 1-D plane, where the i^th point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points.

The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.

Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: n = 4, k = 2

› Output: 3

💡 Note: With 4 points (0,1,2,3), we can draw 2 non-overlapping segments in 3 ways: [0,1]+[2,3], [0,2]+skip 1 point+[3,3], and [1,3]+skip middle points. Wait, segments must cover 2+ points, so [3,3] is invalid. The valid ways are: segments covering [0,1] and [2,3], segments covering [0,2] and skip, actually this needs more careful analysis.

Example 2 — Minimum Case

$ Input: n = 3, k = 1

› Output: 3

💡 Note: With 3 points, we can draw 1 segment in 3 ways: [0,1], [0,2], or [1,2]. Each covers at least 2 points.

Example 3 — Impossible Case

$ Input: n = 3, k = 2

› Output: 0

💡 Note: With only 3 points, we cannot draw 2 non-overlapping segments where each covers at least 2 points.

Constraints

2 ≤ n ≤ 1000
1 ≤ k ≤ n/2

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

This problem uses dynamic programming to count ways to place k non-overlapping line segments. The key insight is that this reduces to a combinatorial problem that can be solved with DP in O(n²k) time or with mathematical formulas in O(k) time.

Common Approaches

✓ Bottom-Up Dynamic Programming

⏱️ Time: O(n²k) Space: O(nk)

Use a 2D DP table where dp[i][j] represents the number of ways to place j non-overlapping segments using the first i points. Build the solution bottom-up by considering each point and segment count.

Mathematical Formula (Combinatorics)

⏱️ Time: O(k) Space: O(1)

The problem reduces to choosing k non-overlapping intervals from n-1 possible positions. This is equivalent to distributing k line segments among n-k+1 gaps, which can be solved using the stars and bars method.

Memoized Dynamic Programming

⏱️ Time: O(n²k) Space: O(nk)

Same recursive approach as brute force but store results of subproblems to avoid recalculating the same state multiple times. Each state is defined by current position and remaining segments.

Recursive Brute Force

⏱️ Time: O(2^n) Space: O(n)

Generate all possible combinations of k non-overlapping line segments by trying each possible starting and ending position for segments recursively. This explores the entire solution space.

Bottom-Up Dynamic Programming — Algorithm Steps

Initialize DP table with base cases
For each point and segment count, calculate ways
Consider placing or not placing a segment ending at current point

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set base cases: dp[i][0] = 1

Fill

For each cell, sum ways from valid previous states

Result

Answer is dp[n][k]

Code -

solution.c — C

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

const int MOD = 1000000007;

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int n, int k) {
    // dp[i][j] = ways to place j segments using first i points
    static long long dp[1005][1005];
    memset(dp, 0, sizeof(dp));
    
    // Base case: 0 segments can be placed in 1 way
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= min(i / 2, k); j++) {
            // Don't place a segment ending at i
            dp[i][j] = dp[i-1][j];
            
            // Place a segment ending at i
            // Try all possible starting points for this segment
            for (int start = 1; start < i; start++) {
                if (start < i) { // Valid segment from start to i
                    dp[i][j] = (dp[i][j] + dp[start-1][j-1]) % MOD;
                }
            }
        }
    }
    
    return dp[n][k];
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    printf("%d\n", solution(n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²k)

Three nested loops: n points × k segments × n possible segment lengths

⚠ Quadratic Growth

Space Complexity

O(nk)

2D DP table with n rows and k+1 columns

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 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

Number of Sets of K Non-Overlapping Line Segments - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler