Cows on a Leash

Cows on a Leash¶

Problem Statement

In [1]:

fin = open ('leash.in', 'r')
# Read in Number of leashes
N = int(fin.readline().strip());
leashlist = []

In [2]:

# read the start and length for each leash
# then compute end point and save (start,end) tuple
# then append onto list of tuples

for i in range(N):
    start, length = map(int,fin.readline().split())
    end = start+length
    temptup = (start,end)
    leashlist.append(temptup)

In [3]:

# sort list of tuples by end time

leashlist.sort(key=lambda x: x[1])

print(leashlist)

[(12, 16), (3, 21), (1, 22), (11, 23), (7, 26), (18, 42), (38, 45), (38, 45), (13, 45), (14, 48), (27, 48), (41, 49), (47, 50), (33, 51), (35, 51), (46, 54), (2, 57), (43, 62), (37, 64), (61, 67), (67, 69), (55, 73), (84, 85), (48, 91), (26, 93), (45, 93), (38, 97), (63, 99)]

In [4]:

# Initialize Counter and 1st Cut
# 1st cut is just before 1st end time

counter = 1
cutpoint = leashlist[0][1]
print("cut just before ", cutpoint)

cut just before  16

In [5]:

# Iterate through sorted list
# each leash is either discarded (if start time was before or equal to last cutpoint)
# or a new cutpoint is defined

for s,e in leashlist:
    
    if s>=cutpoint:
        counter+=1
        cutpoint=e
        print("cut just before ", cutpoint)

    print("leash ",s,e," has been cut")

leash  12 16  has been cut
leash  3 21  has been cut
leash  1 22  has been cut
leash  11 23  has been cut
leash  7 26  has been cut
cut just before  42
leash  18 42  has been cut
leash  38 45  has been cut
leash  38 45  has been cut
leash  13 45  has been cut
leash  14 48  has been cut
leash  27 48  has been cut
leash  41 49  has been cut
cut just before  50
leash  47 50  has been cut
leash  33 51  has been cut
leash  35 51  has been cut
leash  46 54  has been cut
leash  2 57  has been cut
leash  43 62  has been cut
leash  37 64  has been cut
cut just before  67
leash  61 67  has been cut
cut just before  69
leash  67 69  has been cut
leash  55 73  has been cut
cut just before  85
leash  84 85  has been cut
leash  48 91  has been cut
leash  26 93  has been cut
leash  45 93  has been cut
leash  38 97  has been cut
leash  63 99  has been cut

In [6]:

print("Number of Cuts Required:",counter)

Number of Cuts Required: 6