CodingGyan

Activity Selection

medium Data Structures and Algorithms

Problem

There are n activities, each with a start time and an end time. One person can do only one activity at a time, and can start an activity at the same moment when the previous one ends. Print the largest number of activities that the person can do. Input: n, then one line per activity: start and end.

Constraints

  • 1 <= n <= 10^5
  • start < end

Examples

Input

3
1 5
2 3
3 4

Output

2

Solutions

Best approachTime O(n log n)Space O(n)

Choosing the activity that ends first can never hurt: it leaves the largest free time for the rest. After sorting by end time, one pass picks all the activities that fit. O(n log n).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Most activities.
 * Input   : n and the activities.
 * Output  : The count.
 * Approach: Greedy by end time
 * Time    : O(n log n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(String[] lines) {
        int n = Integer.parseInt(lines[0]);
        int[][] activities = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] part = lines[i + 1].split(" ");
            activities[i][0] = Integer.parseInt(part[0]);
            activities[i][1] = Integer.parseInt(part[1]);
        }
        // Step 1: Greedy rule: sort by the end time. The activity that ends first leaves the most time for the others.
        java.util.Arrays.sort(activities, (x, y) -> Integer.compare(x[1], y[1]));
        int count = 0;
        int freeAt = Integer.MIN_VALUE;
        // Step 2: Take an activity if it starts when the last chosen one has ended.
        for (int[] activity : activities) {
            if (activity[0] >= freeAt) {
                count++;
                freeAt = activity[1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}
Hints (1)
  1. Why sort by the end time and not by the start time?

Try these next