Number Of Sets Of K Non Overlapping Line Segments - Leetcode Solution

The Number of Sets of K Non-Overlapping Line Segments problem on LeetCode is a dynamic programming problem that requires finding the number of sets of k non-overlapping line segments that can be formed from n points on the x-axis.

Approach:

1. Sort the given set of points in ascending order.

2. Initialize a two-dimensional array dp[k+1][n] where dp[i][j] represents the number of sets of i line segments that can be formed from the first j points.

3. For i=1 to k and j=1 to n, compute dp[i][j] as follows:

   • If i==1 or j<=i, then dp[i][j] = 1 as there is only one way to form the first line segment and there are not sufficient points to form more than 1 line segment.
   • Else,
     • Initialize a variable max_val = 0 and iterate from the first point to the jth point, and for each point k, check if it can be used as the endpoint of the ith line segment. If it is possible, then update max_val as dp[i-1][k-1] + 1.
     • Compute dp[i][j] as the maximum value of max_val and dp[i][j-1].

4. Return dp[k][n] as the result.

Implementation:

Here is the Python implementation of the above approach.

def maxSets(k: int, n: int) -> int: points = [i for i in range(1, n+1)] dp = [[0]*(n+1) for _ in range(k+1)] for i in range(1, k+1): for j in range(1, n+1): if i==1 or j<=i: dp[i][j] = 1 else: max_val = 0 for k in range(j): if points[j-1]-points[k] > 0: max_val = max(max_val, dp[i-1][k] + 1) dp[i][j] = max(max_val, dp[i][j-1]) return dp[k][n]

Time Complexity: O(k*n^2)

Space Complexity: O(k*n)

The time complexity of the above approach is O(kn^2) and the space complexity is O(kn), which is efficient enough for the given constraints.

1