Solution Notes: Many students used the obvious approach of looping over each of the K ranges, incrementing the array elements in each one. Unfortunately, this is much too slow to run in time on large input cases, so we need to be a bit more clever. As it turns out, it is easy to "implicitly" increment a range without actually looping over all its elements and incrementing them all explicitly. To do this, we keep track of the differences between consecutive elements, instead of the values of the elements themselves. When we increment a range, this only changes two differences -- one at each endpoint of the range. Furthermore, given the differences between consecutive elements, we can rebuild the actual array by scanning through it sequentially and keeping a running sum of all the differences so far. The entire algorithm runs in just O(N+K) time, followed by an O(N log N) sort (there are even fancier algorithms for computing the median of an array in O(N) time without needing to sort, but those are not necessary to obtain full marks for this problem).

import java.util.*;
import java.io.*;
import java.awt.Point;
import static java.lang.Math.*;

public class stacking {
    public static int i(String s) { return Integer.parseInt(s); }
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new FileReader("stacking.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("stacking.out")));
        String[] arr = in.readLine().split(" ");
        int n = i(arr[0]);
        int k = i(arr[1]);
        int[] diff = new int[n+1];

        for(int i=0; i<k; i++) {
            arr = in.readLine().split(" ");
            int A = i(arr[0])-1;
            int B = i(arr[1])-1;
            diff[A]++;
            diff[B+1]--;
        }
        int[] data = new int[n];
        int val = 0;
        for(int i=0; i<n; i++) {
            val += diff[i];
            data[i] = val;
        }
        Arrays.sort(data);
        out.println(data[n/2]);
        out.flush();
    }
}