PYTHON - "Love for Mathematics"

Question

I just finished a challenge on Dcoder ("Love for Mathematics") using Python. I failed two test-cases, but got one right. I used somewhat of a lower level of Python for the same as I haven't explored more yet, so I'm sorry if it looks a bit too basic.The Challenge reads:

Students of Dcoder school love Mathematics. They love to read a variety of Mathematics books. To make sure they remain happy, their Mathematics teacher decided to get more books for them. A student would become happy if there are at least X Mathematics books in the class and not more than Y books because they know "All work and no play makes Jack a dull boy".The teacher wants to buy a minimum number of books to make the maximum number of students happy.

The Input

The first line of input contains an integer N indicating the number of students in the class. This is followed up by N lines where every line contains two integers X and Y respectively.

#Sample Input
5
3 6
1 6
7 11
2 15
5 8

The Output

Output two space-separated integers that denote the minimum number of mathematics books required and the maximum number of happy students.

Explanation: The teacher could buy 5 books and keep student 1, 2, 4 and 5 happy.

#Sample Output
5 4

Constraints: 1 <= N <= 10000 1 <= X, Y <= 10^9

---

My code:

n = int(input())
l = []
mi = []
ma = []
for i in range(n):
  x, y = input().split()
  mi.append(int(x))
  ma.append(int(y))
  if i == 0:
    h=ma[0]
  else:
    if ma[i]>h:
      h=ma[i]

for i in range(h):
  c = 0
  for j in range(len(mi)):
    if ma[j]>=i and mi[j]<=i:
      c+=1
  l.append(c)
great = max(l)
for i in range(1,len(l)+1):
  if l[i]==great:
    print(i,l[i])
    break

---

My Approach: I first assigned the two minimum and maximum variables to two different lists - one containing the minimum values, and the other, the maximum. Then I created a loop that processes all numbers from 0 to the maximum possible value of the list containing maximum values and increasing the count for each no. by 1 every time it lies within the favorable range of students. In this specific case, I got that count list to be (for the above given input): [1,2,3,3,4,4,3,3,2 ...] and so on. So I could finalize that 4 would be the maximum no. of students and that the first index of 4 in the list would be the minimum no. of textbooks required. But only 1 test-case worked and two failed. I would really appreciate it if anyone could help me out here. Thank You.

Answer 1

This problem is alike minimum platform problem.

In that, you need to sort the min and max maths books array in ascending order respectively. Try to understand the problem from the above link (platform problem) then this will be a piece of cake.

Here is your solution:

n = int(input())
min_books = []
max_books = []
for i in range(n):
  x, y = input().split()
  min_books.append(int(x))
  max_books.append(int(y))

min_books.sort()
max_books.sort()

happy_st_result = 1
happy_st = 1
books_needed = min_books[0]

i = 1
j = 0
while (i < n and j < n): 
  if (min_books[i] <= max_books[j]): 
    happy_st+= 1
    i+= 1

  elif (min_books[i] > max_books[j]): 
    happy_st-= 1
    j+= 1

  if happy_st > happy_st_result:
    happy_st_result = happy_st
    books_needed = min_books[i-1]

print(books_needed, happy_st_result)

Try this, and let me know if you need any clarification.

Answer 2

@Vinay Gupta's logic and explanation is correct. If you think on those lines, the answer should become immediately clear to you.

I have implemented the same logic in my code below, except using fewer lines and cool in-built python functions.

# python 3.7.1
import itertools

d = {}
for _ in range(int(input())):
    x, y = map(int, input().strip().split())

    d.setdefault(x, [0, 0])[0] += 1
    d.setdefault(y, [0, 0])[1] += 1

a = list(sorted(d.items(), key=lambda x: x[0]))
vals = list(itertools.accumulate(list(map(lambda x: x[1][0] - x[1][1], a))))

print(a[vals.index(max(vals))][0], max(vals))

The above answer got accepted in Dcoder too.