Challenge: Film Festival

Lab Java Intermediate 20 points

A film festival shows n films, each with a start and end time. You can't watch two at once, but you can start a film at the exact time another ends. What is the most films you can watch? Use the earliest-ending-first greedy rule.

Input

Line 1: n. Then n lines start end (start < end).

Output

The most films.

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

Sort films by end time (a Comparator on int[]).

Take a film if it starts at or after the end of the last film you took.

Solution explanation

Sorting is O(n log n), the scan O(n). Picking the film that ends first never hurts – it leaves the most time free.

Show solution

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class ByEnd implements Comparator<int[]> {
    public int compare(int[] a, int[] b) { return Integer.compare(a[1], b[1]); }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] films = new int[n][2];
        for (int i = 0; i < n; i++) {
            films[i][0] = sc.nextInt();
            films[i][1] = sc.nextInt();
        }
        Arrays.sort(films, new ByEnd());
        int freeAt = Integer.MIN_VALUE, count = 0;
        for (int[] f : films) {
            if (f[0] >= freeAt) {
                count++;
                freeAt = f[1];
            }
        }
        System.out.println(count);
    }
}

Output

Answer