#1621

Number of Sets of K Non-Overlapping Line Segments

specialist · 940 · lc medium +32 · verified · 45.7% accepted · 489 likes · top 29%

Description

Given n integer points at positions 0 through n-1 on a line, count the ways to place exactly k non-overlapping line segments where each segment spans at least 2 points. Segments may share endpoints but not interior points. Return the count modulo 10⁹ + 7.

Example 1:

Input: n = 4, k = 2

Output: 5

Explanation: The two line segments are shown in red and blue.

The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Example 2:

Input: n = 3, k = 1

Output: 3

Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

Example 3:

Input: n = 30, k = 7

Output: 796297179

Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 109 + 7 gives us 796297179.

Code

1

2

3

class Solution:
    def numberOfSets(self, n: int, k: int) -> int:

class Solution:
    def numberOfSets(self, n: int, k: int) -> int: