# Path: tryalgo/interval_cover.py
# def _solve(iles, rayon):
#     II = []
#     for x, y in iles:
#         if y > rayon:
#             return -1               # island is too far
#         z = sqrt(rayon * rayon - y * y)   # find the interval
#         II.append((x + z, x - z))
#     II.sort()                        # sort by right side
#     sol = 0
#     last = float('-inf')
#     for right, left in II:
#         if last < left:             # uncovered interval
#             sol += 1
#             last = right            # put an antenna
#     return sol
# 
# def interval_cover(I):
#     """Minimum interval cover
# 
#     :param I: list of closed intervals
#     :returns: minimum list of points covering all intervals
#     :complexity: O(n log n)
#     """
#     S = []
#     # sort by right endpoints
#     for start, end in sorted(I, key=lambda v: v[1]):
#         if not S or S[-1] < start:
#             S.append(end)
#     return S


import unittest
from tryalgo.interval_cover import _solve, interval_cover
# jill-jênn vie et christoph dürr - 2020
# coding=utf8

# pylint: disable=missing-docstring


class TestIntervalCover(unittest.TestCase):

    def test_solve(self):
        self.assertEqual(_solve([(0, 0), (5, 0)], 3), 1)

    def test_interval_cover(self):
        L = [([(0, 1)], 1),
             ([(0, 3), (1, 2)], 1),
             ([(0, 2), (1, 3)], 1),
             ([(0, 2), (2, 3)], 1),
             ([(0, 2), (3, 4)], 2),
             ([(0, 4), (1, 3), (2, 6), (5, 8), (7, 9), (9, 10)], 3)]
        for instance, res in L:

# Path: tryalgo/interval_cover.py
# def _solve(iles, rayon):
#     II = []
#     for x, y in iles:
#         if y > rayon:
#             return -1               # island is too far
#         z = sqrt(rayon * rayon - y * y)   # find the interval
#         II.append((x + z, x - z))
#     II.sort()                        # sort by right side
#     sol = 0
#     last = float('-inf')
#     for right, left in II:
#         if last < left:             # uncovered interval
#             sol += 1
#             last = right            # put an antenna
#     return sol
# 
# def interval_cover(I):
#     """Minimum interval cover
# 
#     :param I: list of closed intervals
#     :returns: minimum list of points covering all intervals
#     :complexity: O(n log n)
#     """
#     S = []
#     # sort by right endpoints
#     for start, end in sorted(I, key=lambda v: v[1]):
#         if not S or S[-1] < start:
#             S.append(end)
#     return S


# Path: tests/test_interval_cover.py
import unittest
from tryalgo.interval_cover import _solve, interval_cover

# jill-jênn vie et christoph dürr - 2020
# coding=utf8

# pylint: disable=missing-docstring


class TestIntervalCover(unittest.TestCase):

    def test_solve(self):
        self.assertEqual(_solve([(0, 0), (5, 0)], 3), 1)

    def test_interval_cover(self):
        L = [([(0, 1)], 1),
             ([(0, 3), (1, 2)], 1),
             ([(0, 2), (1, 3)], 1),
             ([(0, 2), (2, 3)], 1),
             ([(0, 2), (3, 4)], 2),
             ([(0, 4), (1, 3), (2, 6), (5, 8), (7, 9), (9, 10)], 3)]
        for instance, res in L:

            self.assertEqual(len(interval_cover(instance)), res)