Interval Scheduling Problem

Problem

Given a collection of intervals represented as [start, end], the interval scheduling problem requires identifying the maximum number of non-overlapping intervals from the given collection.

This problem also known as Activity Selection problem.

Examples

Example 1:

1
2
3


Input: [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 3
Explanation: The maximum number of non-overlapping intervals are [1, 2], [2, 3], [3, 4].

Example 2:

1
2
3


Input: [[1, 2], [1, 2], [1, 2]]
Output: 1
Explanation: The maximum number of non-overlapping intervals is [1, 2].

Example 3:

1
2
3


Input: [[1, 2], [2, 3]]
Output: 2
Explanation: Both intervals [1, 2] and [2, 3] are non-overlapping.

Solution

Method 1 - Greedy using sorting

The task can be efficiently solved using a greedy algorithm where we:

Sort the intervals based on their end times.
Use a variable to track the end time of the last added interval.
Iterate through the sorted intervals and select the one that starts after or exactly at the end of the last added interval, thereby maximizing the number of non-overlapping intervals.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


public class Solution {
    public int intervalScheduling(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        // Sort intervals by their end times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int end = Integer.MIN_VALUE;
        int count = 0;

        for (int[] interval : intervals) {
            if (interval[0] >= end) {
                end = interval[1];
                count++;
            }
        }

        return count;
    }

    // Example usage:
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.intervalScheduling(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 3}}));  // Output: 3
        System.out.println(solution.intervalScheduling(new int[][]{{1, 2}, {1, 2}, {1, 2}}));  // Output: 1
        System.out.println(solution.intervalScheduling(new int[][]{{1, 2}, {2, 3}}));  // Output: 2
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def intervalScheduling(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        # Sort intervals by their end times
        intervals.sort(key=lambda x: x[1])
        
        end = float('-inf')
        count = 0
        
        for interval in intervals:
            if interval[0] >= end:
                end = interval[1]
                count += 1
        
        return count
        
# Example usage:
solution = Solution()
print(solution.intervalScheduling([[1, 2], [2, 3], [3, 4], [1, 3]]))  # Output: 3
print(solution.intervalScheduling([[1, 2], [1, 2], [1, 2]]))  # Output: 1
print(solution.intervalScheduling([[1, 2], [2, 3]]))  # Output: 2

Complexity

⏰ Time complexity: O(n log n) for sorting the intervals.
🧺 Space complexity: O(1) as we use a constant amount of extra space (excluding input).

Problem#

Examples#

Solution#

Method 1 - Greedy using sorting#

Code#

Complexity#