Mr. Moneybag's Money Piles
O(K log N), many characters of Python

Edit: Improved by replacing merge sort with radix sort.

This is an improvement over my previous answer, but I'm posting it separately because it's a different strategy, and so the post doesn't get super-long. 

This is now optimal because simply reading the input can take 2*K*lg N time in the worst case -- 2*K numbers each with lg N bits.

The goal is to have minimal dependence on N. To do this, rather than store counts for each pile index, we realize that all piles in a contiguous cluster unaffected by the endpoints of any interval must have the same counts. So, if we see that an interval starts with 5, and there's no changes until 15, then those 10  piles have the same value.

Each change in pile size from a pile to the next one is caused by an interval starting or ending. We call these "events". Each event increases or decreases the current pile size by 1. If, from one event to the next, there's some number of piles, each of those piles has the current size.

We extract the 2*k events from the intervals, and sort them using a radix sort, taking advantage of the values being 1 through N. This take takes O(K*log(N)) because the numbers have O(lg N) bits.  

We then run over the events, and for each one, update the list of counts to the previous event, which requires adding a number up to N (so lg N bits). This takes O(log(N)) per step, and so O(K*log(N))

Finally, having gotten the counts of the pile sizes, it's easy to quickly find the median by computing the cumulative number of piles up to a given size (or, rather, we subtract it from our desired count). This also takes O(K*log(N)).

The algorithm does the huge test case in under a second.

The code (ungolfed) is below with comments.

# Process input
def get_ints(line):
 vals = line.split()
 return (int(vals[0]),int(vals[1]))

s = input()

lines = s.split("\n")
N,K = get_ints (lines[0])
intervals = [get_ints(line) for line in lines[1:]]

mins,maxes=map(list,zip(*intervals))

#Each event will represent an increase or decrease of a pile from the previous one
#Each min increases the count by 1
#Each max causes the count to decrease by 1, starting with the next pile
events = [(a,1) for a in mins] + [(b+1,-1) for b in maxes]
events.append((N+1,0))

#Do a radix sort on the first element of each pair 
#Each number has O(lg N) digits, so this takes O(k lg N) 
events.sort()

#Count of the number of piles of each size
#pile_sizes[size] counts the number of piles of that size
pile_sizes = [0]*K
cur_pile = 1
cur_size = 0

#For each event, we track the pile size after the event
#Then, on the next event, we know there were some number of piles of that size
#The number of piles equals the distance between events
#Multiple events on the same pile have zero distance and don't affect the counts
for event in events:
 event_pile = event[0]
 piles_current_size = event_pile - cur_pile
 pile_sizes[cur_size] += piles_current_size
 cur_pile = event_pile
 cur_size += event[1]

#Get the i_th largest pile size from a list of pile size counts
def get_order_stat(counts,i):
 for val in range(len(counts)):
  cur_count = counts[val]
  if i&lt;cur_count:
   return val
  i-=cur_count
 return None

median = get_order_stat(pile_sizes,N//2)

print(median)