Why does my Python solution for selecting 2 points from each interval give incorrect results for overlapping intervals?

Question

I’m trying to solve the following Leetcode problem:

You are given a 2D integer array intervals where intervals[i] = > [starti, endi] represents all the integers from starti to endi inclusively.

A containing set is an array nums where each interval from intervals has at least two integers in nums.

For example, if intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.

Return the minimum possible size of a containing set.

I wrote the following code:

class Solution:
    def intersectionSizeTwo(self, intervals):
        intervals.sort()
        result = []

        for start, end in intervals:
            count = 0
            for x in result:
                if start <= x <= end:
                    count += 1

            while count < 2:
                val = end - (1 - count)
                result.append(val)
                count += 1

        return len(result)

Issue:

For some test cases, the function produces incorrect results.

Example:

intervals = [[1, 3], [3, 7], [5, 6]]

Expected output (based on known greedy approach):

Actual output from my code:

My questions:

What mistake exists in my logic for choosing points?
Why does picking points backward from the interval’s end sometimes fail with overlapping intervals?
What is the correct greedy strategy to solve this problem?

Any explanation or correction would be appreciated. I'm trying to understand why my approach breaks on certain overlapping cases.

It may just be me, but I cannot reconcile your problem description with your results. You say, "I need to select integers such that each interval contains at least two selected numbers.". I interpret that to mean that we are to specify two integers that are in each interval. Given intervals = [[1, 3], [3, 7], [5, 6]]`, then there are no integers common to these 3 intervals. Yet you think there are 4. Do you have a link to the original problem specification? — Booboo
– Booboo, Commented Nov 21 at 18:19
"I need to select integers": but apparently the output is just a single count. This is not mentioned in your challenge description. Also, while 4 is a correct answer, why would 5 not be right? Did you maybe forget to tell us that this count needs to be minimised? Is there a requirement that no duplicates can be selected? It seems that a few specifications are missing from your question. — trincot
– trincot, Commented Nov 21 at 18:59
I don't think your code makes any attempt to find the smallest set. It may even be returning the length of the largest set. I also don't think it prevents duplicates in result -- use a set instead of list for that. — Barmar
– Barmar, Commented Nov 21 at 19:53
To debug this, print result at various points in the function. — Barmar
– Barmar, Commented Nov 21 at 19:54

Unmitigated · Accepted Answer · 2025-11-21 20:40:33Z

1

You are currently considering intervals in order of their start values, but it is the intervals that end first that decide when values must be chosen. Sort the intervals by the end value instead like so:

import operator
intervals.sort(key=operator.itemgetter(1))

You have also allowed duplicate values in the result list. A simple fix would be to first check existence and try the next number if the current one is already in the result.

i = 0
while count < 2:
    val = end - i
    if val not in result:
        result.append(val)
        count += 1
    i += 1

answered Nov 21 at 20:40

Unmitigated

91.4k12 gold badges102 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Why does my Python solution for selecting 2 points from each interval give incorrect results for overlapping intervals?

Issue:

My questions:

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

Issue:

My questions:

1 Answer 1

Comments

Related