Maximize the Equal Wood Segment Length

Problem Statement

You are given an array of positive integers woods, where each element represents the length of a piece of wood. You are also given an integer k.

You want to cut these pieces of wood to obtain at least k segments of the exact same integer length. You may cut any wood piece into any number of integer-length segments, but you cannot join two pieces together. Any leftover scrap wood that is shorter than the desired length is discarded.

Return the maximum possible integer length of the segments such that you can obtain at least k pieces. If it is impossible to obtain at least k pieces of length at least 1, return 0.

Function Signature

def max_segment_length(woods: list[int], k: int) -> int:
    pass

Examples

Example 1:

Input: woods = [5, 9, 7], k = 4
Output: 4
Explanation:
- Cut woods[0] (5) into 1 piece of length 4 (1 discarded).
- Cut woods[1] (9) into 2 pieces of length 4 (1 discarded).
- Cut woods[2] (7) into 1 piece of length 4 (3 discarded).
Total pieces = 1 + 2 + 1 = 4 pieces of length 4. Length 5 only yields 1 + 1 + 1 = 3 pieces, which is less than k.

Example 2:

Input: woods = [5, 9, 7], k = 3
Output: 5
Explanation:
- Cut woods[0] (5) into 1 piece of length 5.
- Cut woods[1] (9) into 1 piece of length 5 (4 discarded).
- Cut woods[2] (7) into 1 piece of length 5 (2 discarded).
Total pieces = 3 pieces of length 5.

Example 3:

Input: woods = [2, 3], k = 10
Output: 0
Explanation:
The maximum number of 1-unit segments obtainable is 2 + 3 = 5, which is less than k = 10. Thus, return 0.

Constraints

• 1 <= len(woods) <= 10^5
• 1 <= woods[i] <= 10^9
• 1 <= k <= 10^9

Edge Cases

• Total sum of all wood pieces is less than k: the answer must be 0.
• k is 1: the answer is simply the maximum element in woods.
• Large numbers that could cause integer overflow in languages with fixed-width integers (sum of pieces / total length).