Recently had a test and got 0 on my solution with a comment that the algorithm is incorrect (not the proof but the algorithm itself). The counter example they gave is not correct and so I am wondering if was right or is my algorithm actually wrong.

Here is the problem:

Given a set of n jobs (a_1, a_2, ..., a_n) that each have a set start time (s_i) and end time (f_i) (overlaps are very possible), find the smallest subset of jobs A, such that for every job a_i it's either included in A or there exists another job in A a_j, such that a_i and a_j overlap.

As an example:

Given jobs a1(1, 3), a2(2,4), a3(3,5)

Result set A={a2}

Given jobs a1(1, 3), a2(2,4), a3(4,5)

Result set A={a1, a3} or A={a2, a3}

My algorithm:

1. sort the jobs in none descending order by start time (now s_1<= s_2 <= ... <= s_n)

2. let C = a1, M = m = f_1 and A to an empty set.

3. for i=1, 2, ..., n

   3.1) if s_i > M:

      - A = A U {C}
   
   
   
      - C = a_i
   
   
   
      - m = M = f_i
   

   3.2) else if f_i > M and s_i < m:

      - M = f_i
   
   
   
      - C = a_i
   

   3.3) m = min(m, f_i)

4. A = A U {C}

5. return A

Any help is appreciated,

Thanks

Recently had a test and got 0 on my solution with a comment that the algorithm is incorrect (not the proof but the algorithm itself). The counter example they gave is not correct and so I am wondering if was right or is my algorithm actually wrong.

Here is the problem:

Given a set of n jobs (a_1, a_2, ..., a_n) that each have a set start time (s_i) and end time (f_i) (overlaps are very possible), find the smallest subset of jobs A, such that for every job a_i it's either included in A or there exists another job in A a_j, such that a_i and a_j overlap.

As an example:

Given jobs a1(1, 3), a2(2,4), a3(3,5)

Result set A={a2}

Given jobs a1(1, 3), a2(2,4), a3(4,5)

Result set A={a1, a3} or A={a2, a3}

My algorithm:

1. sort the jobs in none descending order by start time (now s_1<= s_2 <= ... <= s_n)

2. let C = a1, M = m = f_1 and A to an empty set.

3. for i=1, 2, ..., n

   3.1) if s_i > M:

      - A = A U {C}
   
   
   
      - C = a_i
   
   
   
      - m = M = f_i
   

   3.2) else if f_i > M and s_i < m:

      - M = f_i
   
   
   
      - C = a_i
   

   3.3) m = min(m, f_i)

4. A = A U {C}

5. return A

Any help is appreciated,

Thanks

• algorithm
• scheduled-tasks
• schedule

Share Improve this question Follow edited Nov 17, 2024 at 15:22 itay elam asked Nov 16, 2024 at 14:13 itay elamitay elam 1122 bronze badges 10

• " find the smallest subset that for every job either includes that job..." this is confusing. I do not know what it means. Please clarify. Provide a small example with the smallest subset that solves this. – ravenspoint Commented Nov 16, 2024 at 14:58
• Best guess: Define a "pyramid" as a 'top job' AND all the jobs that overlap with the 'top job'. The objective, I am guessing, is to create the smallest set of 'pyramids' that include every job input. – ravenspoint Commented Nov 16, 2024 at 15:11
• Note: some jobs may well appear in more than one pyramid. Is that OK with you? – ravenspoint Commented Nov 16, 2024 at 15:13
• Updated the question with an example, eventually you return the smallest set of jobs that qualify for a solution so I guess repetition doesn't matter. – itay elam Commented Nov 16, 2024 at 15:46
• Clarified it a bit more.. hope it is clear now – itay elam Commented Nov 16, 2024 at 17:29

 |  Show 5 more comments

1 Answer 1

Sorted by: Reset to default 2

I had a hard time deciphering your algorithm, but it seems to fail with [1,3], [2,4], [3,5], [4,6], [5,7]

This problem can be solved with a greedy algorithm as follows:

1. Find the interval T with the earliest end time. Note that all intervals that start before T.end will overlap T. From the problem definition, at least one interval that overlaps T is required in the result set;
2. From all the intervals that overlap T (including T), select the one X with the latest end time. This is optimal, because the set of intervals overlapped by X is guaranteed to include any interval overlapped by a candidate with an earlier end time.
3. Copy X into the result set and then delete X and all the intervals it overlaps. The intervals deleted include all intervals with start time before X.end.

It's pretty easy to do this in O(n log n) time by making separate ascending-order lists of the remaining interval end times for step (1), and the remaining interval start times for steps (2) and (3).

Here is an implementation in python:

# input: array of tuples (s,e) with s < e
def minoverlapping(A):
    result = []
    # All intervals sorted by start time.
    # filtered because invalid intervals cause big problems
    bystart = sorted([a for a in A if a[0] < a[1]],
        key = lambda a:a[0])

    # indexes sorted by end time
    ends = sorted(list(range(len(bystart))),
        key = lambda i: bystart[i][1])
    
    delpos = 0    
    for ti in range(len(ends)):
        if bystart[ti] == None:
            # deleted
            continue
        T = bystart[ti]

        # best overlapping interval
        best = T
        while delpos < len(bystart) and bystart[delpos][0] < T[1]:
            x = bystart[delpos]
            bystart[delpos] = None
            delpos += 1
            if x[1] > best[1]:
                best = x
        result.append(best)

        # delete remaining overlaps
        while delpos < len(bystart) and bystart[delpos][0] < best[1]:
            x = bystart[delpos]
            bystart[delpos] = None
            delpos += 1
    return result

tests = [
    [[1,3], [2,4], [3,5], [4,6], [5,7]],
    [(1, 3), (2,4), (3,5)],
    [(1, 3), (2,4), (4,5)]
]

for test in tests:
    print("{0} -> {1}".format(test, minoverlapping(test)))

Output:

[[1, 3], [2, 4], [3, 5], [4, 6], [5, 7]] -> [[2, 4], [5, 7]]
[(1, 3), (2, 4), (3, 5)] -> [(2, 4)]
[(1, 3), (2, 4), (4, 5)] -> [(2, 4), (4, 5)]